Mi máquina de turing simple

Question

Estoy tratando de comprender e implementar la máquina de turing más simple y me gustaría recibir comentarios si tengo sentido.

Tenemos una cinta infinita (digamos una matriz llamada T con el puntero en 0 en el inicio) y la tabla de instrucciones:

(S , R , W , D , N) 

S->STEP (Start at step 1) 
R->READ (0 or 1) 
W->WRITE (0 or 1) 
D->DIRECTION (0=LEFT 1=RIGHT) 
N->NEXTSTEP (Non existing step is HALT) 

Mi entendimiento es que una de 2 símbolos de 3 estados es la máquina más simple . 3-estado no entiendo. 2-symbol porque usamos 0 y 1 para READ/WRITE.

Por ejemplo:

(1,0,1,1,2) 
(1,1,0,1,2) 

empezando en el paso 1, si se lee es 0, entonces {Escribir 1, Mover a la derecha) else {Escribir 0, Mover a la derecha) y luego vaya al paso 2 - lo que no existe que detiene el programa.

¿Qué significa 3-state? ¿Pasa esta máquina como máquina turing? ¿Podemos simplificar más?

Answer 1

Creo que el concepto de estado es básicamente el mismo que en Finite State Machines. Si no recuerdo mal, necesita un estado de finalización por separado, al cual la máquina de turing puede hacer la transición después de que haya terminado de ejecutar el programa. En cuanto a por qué 3 estados, supongo que los otros dos estados son para la inicialización y la ejecución, respectivamente.

Lamentablemente, nada de eso está garantizado para ser correcto, pero pensé que publicaría mis pensamientos de todos modos ya que la pregunta no recibió respuesta durante 5 horas. Sospecho que si volviera a hacer esta pregunta en cstheory.stackexchange.com, podría obtener una respuesta mejor y más definitiva.

Answer 2

"Estado" en el contexto de las máquinas de Turing debe aclararse en cuanto a lo que se describe: (i) la instrucción actual, o (ii) la lista de símbolos en la cinta junto con la instrucción actual, o (iii) la lista de símbolos en la cinta junto con la instrucción actual colocada a la izquierda del símbolo escaneado o a la derecha del símbolo escaneado. Reference

Answer 3

Creo que la confusión podría provenir del uso de "pasos" en lugar de "estados". Puedes pensar en el estado de una máquina como el valor que tiene en su memoria (aunque como se señaló en un cartel anterior, algunas personas también toman el estado de una máquina para incluir el contenido de la cinta; sin embargo, no creo que esa definición sea relevante). a tu pregunta). Es posible que este cambio en la terminología esté en el centro de su confusión. Déjame explicarte qué creo que estás pensando. :)

Has dado listas de cinco números, por ejemplo, (1,0,1,1,2). Como correctamente indica, esto debe interpretarse (leyendo de izquierda a derecha) como "Si la máquina está en el estado 1 Y el cuadrado actual contiene un 0, imprima un 1, muévase a la derecha y cambie al estado 2". Sin embargo, su uso de la palabra "paso" parece sugerir que ese "paso 2" debe ser seguido por "paso 3", etc., cuando en realidad una máquina de Turing puede ir y venir entre estados (y, por supuesto, hay solo pueden ser finitos muchos estados posibles).

Así que para responder a sus preguntas:

• máquinas de Turing no perder de vista "Unidos" no "pasos";
• Lo que has descrito es una máquina legítima de Turing;
• Una máquina de Turing más simple (aunque no interesante) sería una que comience en el estado HALT.

Modificaciones: Gramática, formateo y eliminación de una descripción innecesaria de las máquinas de Turing.

respuesta al comentario: Corrígeme si estoy interpretando mal su comentario, pero yo no tenía intención de sugerir una máquina de Turing podría estar en más de un estado a la vez, sólo que el número de estados posibles puede ser cualquier número finito Por ejemplo, para una máquina de 3 estados, puede etiquetar los posibles estados A, B y C. (En el ejemplo que proporcionó, etiquetó los dos estados posibles como '1' y '2') en cualquier momento dado, exactamente uno de esos valores (estados) estaría en la memoria de la máquina. Diríamos, "la máquina está en el estado A" o "la máquina está en el estado B", etc. (Su máquina comienza en el estado '1' y termina después de que ingresa al estado '2').

Además, ya no tengo claro a qué te refieres con una máquina "más simple/est". La máquina Universal Turing más pequeña conocida (es decir, una máquina Turing que puede simular otra máquina Turing, con una cinta apropiada) requiere 2 estados y 5 símbolos (ver the relevant Wikipedia article).

Por otro lado, si está buscando algo más simple que una máquina de Turing con el mismo poder de cálculo, Post-Turing machines podría ser de su interés.