Una vez jugué a un juego relacionado con la programación. Se trataba de escribir un programa para colocar cosas en una cinta transportadora.

Una máquina de Turing es una tupla de siete (Q, Σ, Γ, δ, q0, qaccept, qreject), donde Q, Σ, Γ son todos conjuntos finitos y satisfacen

Q es el estado establecido?

2.Σ es el alfabeto de entrada, que no contiene el carácter especial de espacio en blanco □?

3.Γ es el alfabeto con?, ¿dónde? □∈Γ y Σ∈Γ ;?

4. δ:Q×　→Q×Γ×{L,R} es la función de transferencia, donde L,R representa si el cabezal de lectura-escritura se mueve hacia la izquierda o se mueve hacia la derecha;?

5.q0∈Q es el estado inicial;?

6.qaccept es el estado de aceptación?

7.qreject es estado de rechazo, y. qreject≠qaccept

La máquina de Turing M = (Q,Σ,Γ,δ,q0,qaccept,qreject) funcionará de la siguiente manera:

Al principio, la cadena de símbolos de entrada ? se completa en la cuadrícula No. ? de la cinta de papel de izquierda a derecha, y las otras cuadrículas permanecen en blanco (es decir, llenas de caracteres en blanco). El cabezal de escritura de M apunta a la cuadrícula No. 0 y M está en el estado q0. Después de iniciar la operación, el cálculo se realiza de acuerdo con las reglas descritas por la función de transferencia δ. q y el símbolo en la cuadrícula señalado por el cabezal de lectura-escritura es x, sea δ(q,x) = (q',x',L), entonces la máquina ingresa al nuevo estado q&#. 39;, cambia el símbolo en la cuadrícula apuntado por el cabezal de lectura y escritura a x', y luego mueve el cabezal de lectura y escritura una cuadrícula hacia la izquierda. En un momento determinado, el cabezal de lectura y escritura apunta a la cuadrícula. No. 0, pero de acuerdo con la función de transferencia, continuará moviéndose hacia la izquierda en el siguiente paso. En otras palabras, el cabezal de lectura y escritura nunca se sale del papel. límite izquierdo de la banda si en un momento determinado M ingresa al estado qaceptar según la función de transferencia, se detiene inmediatamente y acepta la cadena de entrada si en un momento determinado M ingresa al estado qrechazar según la función de transferencia, se detiene inmediatamente; y rechaza la cadena de entrada.

Tenga en cuenta que la función de transferencia δ es una función parcial. En otras palabras, para algunos q,x, δ(q,x) puede no estar definido si se encuentra el siguiente. durante la operación Si la operación no está definida, la máquina se detendrá inmediatamente