¿Por qué el símbolo en blanco no se considera parte del alfabeto de entrada de una máquina Turing?

Las definiciones de las máquinas de Turing son siempre explícitas sobre el símbolo en blanco que no forma parte del alfabeto de entrada.

Me pregunto qué sale mal cuando lo harías parte del alfabeto de entrada, porque efectivamente el símbolo en blanco ya parece ser parte de la entrada.

Para explicar que "parece" en la última oración, considere lo siguiente.

En la configuración predeterminada, aparece un número infinito de símbolos en blanco a la derecha de la entrada. Cuando el cabezal de la cinta se mueve sobre el primer símbolo en blanco, el cálculo puede continuar, ya que no necesita ser un estado de aceptación o rechazo.

Ahora suponga que el cálculo posteriormente escribiría símbolos del alfabeto de entrada a la derecha de ese primer símbolo en blanco, luego volvería a la posición más a la izquierda y al mismo tiempo volvería al estado inicial. Entonces 'comenzaría de nuevo' con una cinta diferente. Efectivamente, ahora comienza con una entrada diferente, donde hay símbolos de entrada a la derecha del espacio en blanco que no estaban allí antes. La entrada parece incluir efectivamente el símbolo en blanco. El comportamiento adicional de la máquina ahora también podría ser diferente: después de encontrar el espacio en blanco nuevamente, ahora encontrará diferentes símbolos a la derecha.

Suponiendo que este escenario sea realmente posible, ¿por qué no consideraría que el símbolo en blanco es parte del alfabeto de entrada y por qué no permitiría incluirlo como parte de la entrada 'inicial'?

¿Quizás es solo una forma de definir la entrada de manera que no siempre sea infinita?

turing-machines Confusión
fuente

Cuando estaba en clase, diseñé máquinas de Turing que utilizaban permitir β (el símbolo en blanco local) en su entrada como separadores de campo.

Joshua

Respuestas:

La razón principal es que permite que la máquina detecte el final de su entrada: es (el carácter anterior) el primer espacio en blanco. Si permitía espacios en blanco en la entrada, la máquina nunca podría saber si podría encontrar más entradas escaneando más a la derecha. Por supuesto, puede resolver eso teniendo un carácter especial de "fin de entrada", pero luego debe insistir en que eso no puede aparecer en la entrada, por lo que acaba de cambiar el problema un nivel más profundo.

También hace que las condiciones iniciales sean mucho más fáciles de especificar: la entrada es la sección no en blanco de la cinta inicial, que debe ser finita y contigua. Y si desea que un carácter en blanco forme parte del alfabeto de entrada, siempre puede agregar un carácter adicional (llámelo "espacio" o algo así) y haga que la máquina se comporte como quiera cuando lo vea.

David Richerby
fuente

Ah, por supuesto, sin poder determinar el final de la entrada inicial, algunos cálculos serían imposibles. Pero por lo demás no hay nada especial sobre el símbolo. Y supongo que es cuestión de economía terminológica usar el símbolo en blanco, ya que de todos modos lo necesita en su alfabeto. Creo que habría sido más obvio para mí cuando se definió inicialmente con un símbolo explícito de fin de entrada y un comentario que no era estrictamente necesario y que a menudo se omitía.

Confusión

{00} \to 0, {11} \to 1, {10, 01} \to b

$\{00\} \rightarrow 0, \{11\} \rightarrow 1, \{10, 01\} \rightarrow b$

Ya que la máquina de Turing necesita reglas que rijan lo que hace si lee un espacio en blanco, y puede tener una regla que le diga que escriba un espacio en blanco, ¿no significa eso que el espacio en blanco es parte de su alfabeto? No veo por qué la entrada puede no contener espacios en blanco. ¿Qué tal codificar elementos de entrada utilizando los caracteres no en blanco y un solo espacio en blanco como separador? Luego, varios espacios en blanco consecutivos indican el final de la entrada.

Rosie F

@YonatanN Claro. Eso es "simple" pero tener un símbolo en blanco es más simple.

David Richerby

@RosieF El espacio en blanco es parte del alfabeto de la cinta; el alfabeto de entrada es un subconjunto de eso. Y, claro, podría establecer convenciones sobre cómo la entrada puede contener espacios en blanco en ciertas circunstancias (como lo hizo), pero eso solo hace que las definiciones sean más complejas. Las definiciones más complejas significan que es más difícil demostrar cosas sobre las máquinas Turing. Y, dado que las máquinas Turing realmente solo se usan para probar cosas (si desea diseñar una computadora real, no será una TM), eso no es una buena compensación.

David Richerby

Puede definir el símbolo en blanco como parte del alfabeto. El problema con eso es que si una máquina de Turing con entrada b010010b (donde b significa en blanco ) nunca lee más allá de la segunda b, entonces la máquina se comportará exactamente de la misma manera en todas las entradas que comienzan con b010010b.

Estas máquinas de Turing se denominan máquinas de Turing con prefijo , y son muy útiles para probar algunos teoremas sobre la complejidad de Kolmogorov.

Peter Shor
fuente

Respuesta muy breve: el alfabeto de la cinta es el conjunto de símbolos que pueden aparecer en la cinta e incluye el símbolo en blanco. El alfabeto de entrada es el conjunto de símbolos que pueden aparecer en la entrada inicial , y no incluye el símbolo en blanco. El alfabeto principal que le importa a la máquina es el alfabeto de cinta: todavía necesita reglas sobre qué hacer cuando ve un espacio en blanco, por ejemplo.

Esta distinción es importante, como han dicho otros, para que la máquina pueda saber dónde termina su entrada. Es la misma razón por la que no puede (útilmente) poner un carácter cero en el medio de una cadena en C: el carácter cero está reservado para significar "el último carácter distinto de cero antes de que este sea el final de los datos, entonces cuando veas esto, ya terminaste ". Si necesita esperar cero caracteres en el medio de la cadena, la escritura se strlenvuelve mucho más difícil.

Draconis
fuente