1. Inicios de la Máquina de Turing

En el año 1931, Kurt Gödel publicó su famoso artículo Sobre las proposiciones formalmente indecidibles en Principia mathematica y sistemas relacionados, el cual en síntesis demuestra que toda formulación axiomática consistente de la teoría de números contiene proposiciones indecidibles, es decir, siempre habrá en ella afirmaciones verdaderas que no se pueden demostrar.

K. Gödel con A. Einstein

En 1937, el matemático inglés Alan Turing publicó otro artículo famoso (sobre los Números Calculables), que desarrollo el teorema de Gödel y que puede considerarse el origen oficial de la informática teórica. En este artículo introdujo la Máquina de Turing, una entidad matemática abstracta que formalizó el concepto de algoritmo, convirtiéndose en la precursora de las computadoras digitales. Con la ayuda de su máquina, Turing pudo demostrar que existen problemas irresolubles, tales que ninguna máquina u ordenador serán capaces de obtener su solución. Por esta razón, Turing es considerado el padre de la teoría de la computabilidad.

A. Turing

En forma general, una Máquina de Turing puede considerarse como una cinta infinita dividida en casillas, cada una de las cuales contiene un símbolo. Sobre dicha cinta actúa un dispositivo que puede adoptar diversos estados y que, en cada instante, lee un símbolo de la casilla sobre la que está situado. En función del símbolo que ha leído y del estado en que se encuentra, realiza las tres acciones siguientes: pasa a un nuevo estado, imprime un símbolo en lugar del que acaba de leer y se desplaza a una posición hacia la izquierda, derecha, o se detiene.