Descripción informal

                                 Descripción informal 

La máquina de Turing modela matemáticamente a una máquina que opera mecánicamente sobre una cinta. En esta cinta hay símbolos que la máquina puede leer y escribir, uno a la vez, usando un cabezal lector/escritor de cinta. La operación está completamente determinada por un conjunto finito de instrucciones elementales como "en el estado 42, si el símbolo visto es 0, escribe un 1; Si el símbolo visto es 1, cambia al estado 17; en el estado 17, si el símbolo visto es 0, escribe un 1 y cambia al estado 6; etc". En el artículo original ("Sobre números computables con una aplicación al Entscheidungsproblem"), Turing no imagina un mecanismo, sino una persona a la que él llama la "computadora", quien ejecuta servilmente estas reglas mecánicas deterministas (o como Turing pone, "de una manera desganada").

Más precisamente, una máquina de Turing consta de:

Una cinta que se divide en celdas, una al lado de la otra. Cada celda contiene un símbolo de algún alfabeto finito. El alfabeto contiene un símbolo especial llamado blanco (aquí escrito como 'B') y uno o más símbolos adicionales. La cinta se supone que es arbitrariamente extensible hacia la izquierda y hacia la derecha, es decir, la máquina de Turing siempre es provista con tanta cinta como necesite para su computación. Las celdas que no se hayan escrito previamente se asumen que están rellenas con el símbolo blanco. En algunos modelos la cinta tiene un extremo izquierdo marcado con un símbolo especial; la cinta se extiende o es indefinidamente extensible hacia la derecha.Un cabezal que puede leer y escribir símbolos en la cinta y mover la cinta a la izquierda y a la derecha una (y solo una) celda a la vez. En algunos modelos el cabezal se mueve y la cinta es estacionaria.Un registro de estado que almacena el estado de la máquina de Turing, uno de los estados finitos. Hay un estado inicial especial con el que el registro de estado se inicia. Turing escribe que estos estados reemplazan el "estado de la mente" en que ordinariamente estaría una persona realizando cálculos.Una tabla finita de instrucciones (llamada ocasionalmente como tabla de acción o función de transición). Las instrucciones son usualmente 5-tuplas: qiaj→qi1aj1dk, (a veces 4-tuplas), que, dado el estado (qi) en que la máquina se encuentra actualmente y el símbolo (aj) que se está leyendo en la cinta (el símbolo actualmente debajo del cabezal) le indica a la máquina hacer lo siguiente en secuencia (para los modelos de 5-tupla):Borra o escribe un símbolo (reemplazando aj con aj1), y entoncesMueve el cabezal (que es descrito por dk y puede tener los valores: 'L' para un paso a la izquierda, o 'R' para un paso a la derecha, o 'N' para permanecer en el mismo lugar) y luegoAsume el mismo o un nuevo estado como prescrito (ve al estado qi1).En los modelos de 4-tupla, son especificadas como instrucciones separadas: borrar o escribir un símbolo (aj1) y mover el cabezal a la izquierda o la derecha (dk). Específicamente, la tabla indica a la máquina: (ia) borrar o escribir un símbolo o (ib) mover el cabezal a la izquierda o a la derecha, y luego (ii) asumir el mismo o un nuevo estado, pero no las dos acciones (ia) y (ib) en la misma instrucción. En algunos modelos, si no hay ninguna entrada en la tabla para la actual combinación de símbolo y estado, la máquina se detendrá; otros modelos requieren que estén llenas todas las entradas.

Note que cada parte de la máquina — su estado y colecciones de símbolos — y sus acciones — imprimir, borrar, movimiento de la cinta — es finito, discreto y distinguible; es la cantidad potencialmente ilimitada de cinta lo que le da una cantidad ilimitada de espacio de almacenamiento.