¿Qué tipo de cosa es una máquina de Turing?

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

1.Q es el conjunto de estados;

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

3.Γ es el alfabeto con □, donde □ ∈Γ y Σ∈Γ;

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

5.q0∈Q es el estado inicial;

6 qaccept es el estado de aceptación. el estado de rechazo, y ≠qaccept

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

En Al principio, la cadena de símbolos de entrada será desde la izquierda. Vaya a la derecha y complete la cuadrícula No. 1 de la cinta de papel, y las otras cuadrículas permanecerán en blanco (es decir, llenas de caracteres en blanco). de M apunta a la cuadrícula No. 0 Después de que la máquina comienza a funcionar en el estado q0, sigue la función de transferencia Calcule de acuerdo con las reglas descritas por δ. Por ejemplo, si el estado actual de la máquina es q y el símbolo en la cuadrícula. apuntado por el cabezal de lectura-escritura es x, sea δ(q,x) = (q',x',L), luego la máquina ingresa al nuevo estado q', cambia el símbolo en la cuadrícula señalado por el cabezal de lectura-escritura diríjase a x ', y luego mueva el cabezal de lectura y escritura una cuadrícula hacia la izquierda. Si en un momento determinado, el cabezal de lectura y escritura apunta al número 0. cuadrícula, pero continuará moviéndose hacia la izquierda de acuerdo con la cuadrícula. función de transferencia, y se detendrá en su lugar. En otras palabras, el cabezal de lectura y escritura nunca se moverá fuera del límite izquierdo de la cinta de papel si M ingresa de acuerdo con la función de transferencia. Si ingresa al estado qaceptar, lo hará inmediatamente. detener y aceptar la cadena de entrada; si en un momento determinado M ingresa al estado qreject de acuerdo con la función de transferencia, inmediatamente se detendrá y rechazará la cadena de entrada.

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

La idea básica de Turing. La idea básica es utilizar máquinas para simular el proceso de las personas que utilizan papel y bolígrafo para realizar operaciones matemáticas. Considera dicho proceso como las siguientes dos acciones simples:

Escribir o borrar un determinado símbolo en el papel.

Mover la atención de una posición en el papel a otra;

En cada etapa, la persona tiene que decidir el siguiente paso. La acción depende de (a) el símbolo en un determinado lugar. posición en el papel al que la persona está prestando atención actualmente y (b) el estado de pensamiento actual de la persona.

Para simular este proceso de cálculo humano, Turing construye una máquina imaginaria, que consta de lo siguiente. partes:

1. Una cinta de papel infinitamente larga CINTA. La cinta de papel se divide en pequeñas cuadrículas una tras otra, cada cuadrícula contiene un símbolo de un alfabeto limitado y hay un símbolo especial en el alfabeto para representar el espacio en blanco. Las cuadrículas de la cinta de papel están numeradas 0, 1, 2,... de izquierda a derecha, y el extremo derecho de la cinta de papel se puede extender infinitamente.

2. Un cabezal de lectura-escritura HEAD. El cabezal de lectura y escritura puede moverse hacia la izquierda y hacia la derecha en la cinta de papel. Puede leer los símbolos en la cuadrícula actual y cambiar los símbolos en la cuadrícula actual.

3. Un conjunto de reglas de control TABLA. Determina la siguiente acción del cabezal de lectura-escritura en función del estado actual de la máquina y el símbolo en la cuadrícula señalado por el cabezal de lectura-escritura actual, y cambia el valor del registro de estado para que la máquina entre en un nuevo estado. .

4. Un registro de estado. Se utiliza para guardar el estado actual de la máquina de Turing. El número de todos los estados posibles de una máquina de Turing es finito y existe un estado especial llamado estado de detención. Ver problema de apagado.

Tenga en cuenta que cada parte de esta máquina es finita, pero tiene una longitud de cinta de papel potencialmente infinita, por lo que esta máquina es solo un dispositivo ideal. Turing creía que una máquina así podría simular cualquier proceso computacional que los humanos puedan realizar.

En algunos modelos, la cinta se mueve y la cinta no utilizada queda realmente "en blanco". El comando a realizar (q4) se muestra encima del escaneo al cuadrado (dibujado por Kleene (1952) p.375).

En algunos modelos, el cabezal de lectura/escritura se mueve a lo largo de una cinta de papel fija. El comando a ejecutar (q1) se muestra en el cabezal de lectura/escritura. La cinta "en blanco" de este modelo es toda ceros. Los cuadrados sombreados, incluidos los espacios en blanco escaneados por el cabezal de lectura y escritura, los cuadrados marcados con 1, 1, B y el símbolo del cabezal de lectura y escritura, constituyen el estado del sistema. (Dibujo de Minsky (1967) p.121).