¿Cuál es la diferencia entre detener, aceptar y decidir en el contexto de las máquinas de Turing?

10

¿Aceptar significa que el TM leerá y reconocerá un carácter de la celda de la que está leyendo actualmente? ¿Y es el caso de que una TM se detenga si la entrada es decidible?

sdfasdgasg
fuente
Detener es sinónimo de terminar (en un estado de aceptación / rechazo). Aceptar un idioma (decidir la membresía en un idioma) significa detenerse en un estado de aceptación de todas las entradas que pertenecen al idioma.
saadtaame
Esta es una cuestión de definiciones básicas. ¿Qué te ha estado confundiendo?
Raphael

Respuestas:

10

Aceptar y rechazar el estado en el que eventualmente puede ingresar una máquina de Turing se basa en la cadena leída de la cinta, no solo en el símbolo de una celda. Por supuesto, la decisión de ingresar una cinta de aceptación o rechazo se toma en última instancia sobre la base de un símbolo.

Una máquina de Turing puede eventualmente ingresar a un estado de aceptación, ingresar a un estado de rechazo o hacer un ciclo para siempre. Si entra en un estado de aceptación o rechazo, entonces se detiene.

Se dice que una máquina de Turing es total si se detiene en todas las entradas.

El lenguaje aceptado por una máquina de Turing es el conjunto de todas las palabras que, cuando se proporcionan como entrada a la máquina de Turing, hacen que la máquina de Turing entre en un estado de aceptación.

Se dice que un idioma es decidible si y solo si existe una máquina Turing total que acepte el idioma.

Dave Clarke
fuente
En realidad, deberíamos estar hablando de los programas de máquina de Turing. La máquina de Turing en sí misma es un modelo. Es un abuso de la expresión.
saadtaame