¿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?
terminology
turing-machines
undecidability
sdfasdgasg
fuente
fuente
Respuestas:
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.
fuente