La máquina de Turing es un modelo
computacional introducido por Alan Turing en el trabajo “On computable numbers,
with an application to the Entscheidungsproblem”, publicado por la Sociedad
Matemática de Londres, en el cual se estudiaba la cuestión planteada por David
Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método
definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si
esa sentencia es cierta o no. Turing construyó un modelo formal de computador,
la máquina de Turing, y demostró que existían problemas que una máquina no
podía resolver. La máquina de Turing es un modelo matemático abstracto que
formaliza el concepto de algoritmo. Una máquina de Turing con una sola cinta
puede ser definida como una 6-tupla , donde Q es un conjunto finito de estados
Γ es un conjunto finito de símbolos de cinta, el alfabeto de cinta
es el estado inicial
es un símbolo denominado blanco, y es el único
símbolo que se puede repetir un número infinito de veces
es el conjunto de estados finales de
aceptación
es una función parcial denominada función de
transición, donde L es un movimiento a la izquierda y R es el movimiento a la
derecha.
