Me he preguntado por qué las cintas / cintas no son parte de la definición formal de una máquina de Turing. Considere, por ejemplo, la definición formal de una máquina de Turing en la página de Wikipedia . La definición, siguiendo a Hopcroft y Ullman, incluye: el conjunto finito de estados , el alfabeto de cinta , el símbolo en blanco , el estado inicial , el conjunto de estados finales , y la función de transición . Ninguno de los cuales es la cinta en sí. b ∈ Γ q 0 ∈ Q F ⊆ Q δ : ( Q ∖ F ) × Γ → Q × Γ × { L , R }
Una máquina de Turing siempre se considera que funciona en una cinta, y la función de transición se interpreta como mover la cabeza, sustituir el símbolo y cambiar el estado. Entonces, ¿por qué la cinta queda fuera de la definición matemática de una máquina de Turing?
Por lo que puedo ver, la definición formal en sí misma no parece implicar que la máquina de Turing funcione como a menudo se describe informalmente (con una cabeza moviéndose en una cinta). O lo hace?
fuente
Respuestas:
Para definir formalmente una instancia de una máquina de Turing (no el concepto general), no necesita mencionar explícitamente la cinta en sí o sus contenidos. Para denotar una configuración de esta máquina en particular, o un cálculo realizado por ella, es cuando necesita alguna forma de notación para describir el contenido de la cinta.
fuente
Es un área un poco gris, pero diría que la definición divide el modelo de la instancia . Si desea tener una idea simple en mente, piense en hardware vs software.
El modelo es el hardware: es una cabeza. Hay una cinta La cinta es infinita en un lado y contiene espacios en blanco (además de la entrada). La cabeza puede moverse paso a paso.
La instancia es el software: la entrada dicta lo que la cinta contiene al principio, la función de estado / transición indica cómo se mueve el cabezal y cómo "funciona" la máquina. Los estados finales dan el significado de éxito / fracaso.
Ambos parámetros son configurables --- ambos se pueden cambiar. Existen modelos alternativos con dos cintas, dos cabezales, cintas de dos lados, cinta no vacía, etc. Pero una vez que arregle el modelo, debe resolver los otros parámetros "configurables", como el número de estados posibles y la función de transición .
¿Qué hace que un parámetro sea parte del modelo en lugar de ser parte de la instancia? Eso es solo un área gris, y no creo que haya una buena respuesta (tal vez me equivoque. ¿Alguien?). Parece que separarse a "Hardware" / "Software" tiene más sentido clasificar parámetros como parte del modelo o parte de la instancia, pero podemos imaginar otros universos en los que esta clasificación es diferente (por ejemplo, donde TM es un 8-tuplas, que también contienen = la posición de la cabeza al principio, o = el número de cintas, o = un patrón que aparece repetidamente en la cinta después del final de la entrada, etc.)M p a t t e r nP M pattern
fuente
Aquí ya hay buenas respuestas, pero trato de hacer una sucinta.
Las definiciones no deben ser excesivas o detalladas.
De hecho, la definición de máquina de Turing define la abstracción de la cinta también. El q0 - es el comienzo de la cinta. El alfabeto es un contenido de la cinta. Y δ: (Q ∖ F) × Γ → Q × Γ × {L, R} indica que la cinta tiene izquierda y derecha e infinito en ambas direcciones.
Entonces, la cinta, la cabeza, se mueve solo representaciones del modelo amigables para los humanos, ya están en el modelo matemático , pero no son un modelo formal en sí mismos.
fuente
Les proporciona una respuesta concisa y correcta: las definiciones matemáticas son lo más concisas posible, e incluir explícitamente una cinta infinita en la definición de una máquina de Turing haría que su definición fuera mucho menos concisa, por lo que no lo hacemos.
Esto no responde la pregunta: ¿por qué ? ¿Cómo puede la definición excluir la cinta infinita cuando la necesitamos?
La respuesta: nosotros no. En cierto sentido, las máquinas de Turing en realidad no requieren cintas infinitas, y su definición lo deja claro.
Por definición, el movimiento de una máquina de Turing lleva la máquina de una configuración a otra; una configuración incluye una cadena finita , que consideramos como un fragmento finito de cinta escrita. Cada movimiento mueve el cabezal de la cinta una posición o sobrescribe el símbolo debajo del cabezal de la cinta. Sin embargo, y esto es esencial para su funcionamiento:
Entonces, para que las máquinas Turing arbitrarias funcionen indefinidamente, se requiere un suministro infinito de celdas de cinta en blanco en ambos extremos. Mientras tanto, en cualquier punto, su configuración, que describe la extensión de la cinta en la que ha escrito, siempre es finita: después de pasos, el cabezal de la cinta nunca puede haberse desviado más de celdas desde su punto de partida.n n
Una forma de reformular esto es decir: la máquina funciona con una cinta infinita, completamente llena de espacios en blanco, excepto por un fragmento finito en el que se encuentra la cabeza de la cinta. Esto es lo que dicen la mayoría de las explicaciones.
Otra forma de reformular esto es decir: la máquina funciona con una cinta finita, extendida con espacios en blanco cada vez que su cabeza se separa de la cinta en cada extremo.
Ambas son formas válidas de conceptualizar cómo funciona la máquina: en ambos casos, si realmente tuviera una máquina que funcionara así, implementaría correctamente una máquina de Turing.
Si todo lo que le interesa es enseñar a los estudiantes cómo funcionan las máquinas de Turing, probablemente no importa qué conceptualización elija.
Sin embargo, creo que la primera conceptualización es un error, por dos razones:
En resumen: la idea de que las máquinas de Turing utilicen o contengan una cinta infinita sirve para enfatizar un punto técnico importante, pero no es necesariamente la forma más intuitiva de pensar acerca de las máquinas de Turing, e invita a ciertas conclusiones incorrectas. Usar con precaución.
fuente