Historia (Teoría de la Computación)

(Resumen tomado y modificado de Wikipedia)

Los antecedentes de la computación mecánica, pueden trazarse hasta épocas antiguas, con el desarrollo de artefactos para asistir el proceso de los cálculos matemáticos mentales, por ejemplo el ábaco, la regla de cálculo o el quipu.

Otro ejemplo precursor son las máquinas sumadoras de Blaise Pascal. Destacando Kurt Gödel y Bertrand Russell entre otros.

Varias definiciones y modelos formales de lo que es un cálculo fueron propuestos por precursores del dominio como Alan Turing y Alonzo Church; entre esos modelos están la máquina de Turing, las funciones recursivas, y el cálculo Lambda.

Se asume normalmente que las computadoras electrónicas son también equivalentes en capacidad de cómputo a cualquiera de esos tres modelos mencionados anteriormente (si se asume que una computadora puede tener memoria infinita), pero no existe una prueba formal de ello (igualmente que no existen contraejemplos), por tal razón a tal presunción razonable se le conoce como la conjetura de Church-Turing.

Es meritorio el hecho que gracias a la equivalencia de máquinas de Turing y computadoras, se haya determinado que existen cálculos que no pueden ser resueltos en un tiempo razonable en ninguna computadora imaginable, o incluso, que no pueden resolverse en lo absoluto, por ejemplo el problema de correspondencia de Post o el problema de predecir si una máquina de Turing cualquiera va a llegar a un estado final (conocido como el problema del halting en inglés, o problema de la parada).

Se ha determinado que existen cómputos resolubles, pero que necesitan cantidades irrealistas de tiempo o memoria para poder efectuarse.

Otro interés de esta ciencia, son los modelos reducidos de cómputo, que son en realidad casos particulares de una máquina de Turing. Como lo son las máquinas de estado finito esbozadas primero por Warren McCulloch y Walter Pitts en 1943, y los autómatas con pila.