, donde 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.
La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:
* avanzar el cabezal lector/escritor para la derecha.
* avanzar el cabezal lector/escritor para la izquierda.
El cómputo es determinado a partir de una tabla de estados de la forma:
(estado, valor) \rightarrow (\nuevo estado, \nuevo valor, dirección)
Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a ser escrito en la cinta.
Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar.
Mediante este modelo teórico y el análisis de complejidad de algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones en tiempo polinómico son encontradas según el determinismo y no determinismo respectivamente de la máquina de Turing.
Esta Maquina de Turing es Capaz de representar la expresion {a^nb^nc^n n>=0} lo cual un automata de pila no puede hacer haciendo utilización de una sola pila.