Entrada y salida de una máquina de Turing

Para algunos modelos de máquinas de computación, no hay duda de cuál es su entrada y salida: es solo el contenido de algunas "celdas" específicas, por ejemplo, en una "cinta" isomorfa a norte .

Considere, por ejemplo , autómatas finitos con una cabeza estática: la entrada se puede ver como la secuencia de tiempo de los símbolos en la celda 0 hasta la primera aparición (en el tiempo) del símbolo en blanco (= fin de entrada) b .

Alternativamente (cuando el autómata puede mover la cabeza hacia la derecha), la entrada puede verse como los símbolos en una secuencia espacial de celdas que comienzan en la celda 0 hasta la primera aparición (en el espacio) de b .

Para máquinas de Turing (especialmente con un norte -cinta) no es de ninguna manera obvio lo que debe considerarse como la entrada y la salida de una máquina dada T junto con una cinta inicial I y su correspondiente cinta final O (asumiendo que T se detiene en I ).

Las posibles "definiciones" genéricas de lo que debe considerarse como "entrada" son:

  • la cinta inicial completa I
  • la secuencia más corta que comienza en la celda 0 que contiene todos los símbolos que no están en blanco
  • la parte de la cinta que ha sido visitada, finalmente
  • las celdas visitadas que "marcaron la diferencia"

Por "hacer una diferencia" me refiero a lo siguiente: algunas celdas se visitan solo para escribir resultados intermedios en ellas, independientemente de su contenido inicial. El contenido inicial de esas celdas no marca la diferencia y no debe contarse como entrada.

También hay "definiciones" basadas en la aparición de marcadores de "fin de entrada":

  • la secuencia que comienza en la celda 0 hasta la primera aparición del símbolo en blanco b
  • la secuencia que comienza en la celda 0 hasta la primera aparición de la palabra w (que puede contener símbolos arbitrarios del alfabeto de la cinta)

También hay "definiciones" basadas en la posición de la cabeza, por ejemplo, las definiciones anteriores con "comenzando en la celda 0 "reemplazado por "comenzando en la posición de la cabeza".

Algunas de estas "definiciones" pueden -en casos especiales- coincidir con otra.

Lo que he aprendido hasta ahora:

  • "entrada" y "salida" no son una parte explícita de la definición de máquinas de Turing.

  • A veces se establece por "convención" cómo debe darse la entrada y cómo debe verse la salida (véase, por ejemplo, Cooper, Computability Theory , p. 37).

El problema con las convenciones (de entrada) es: si no las sigue y pone algunas cifras adicionales en la cinta inicial, la máquina de Turing funciona de todos modos y eventualmente produce alguna salida, eventualmente diferente de la salida sin las cifras adicionales.

Lo que me pregunto:

  • ¿Qué papel se supone que juegan tales convenciones y cómo?

  1. ¿Deberíamos simplemente descuidar las entradas no convencionales (y simplemente no preocuparnos de cómo las procesa una máquina de Turing)?

  2. ¿Deberíamos simplemente descuidar las máquinas de Turing no convencionales (que no producen salidas convencionales para todas las entradas convencionales)?

Independientemente de las convenciones:

  • ¿Existe realmente un problema conceptual con la "entrada" y la "salida" de las máquinas de Turing?
  • Si no es así: ¿por qué no?
  • Si es así: ¿Dónde puedo obtener más información al respecto?
"Marcar una diferencia" no es conceptualmente bueno, ya que entonces no hay una forma obvia de determinar si dos entradas son "iguales".
Eso depende de cuáles sean las dos entradas.

Respuestas (2)

Creo que no es un "problema conceptual real".

Pero si desea una codificación sin ambigüedades, puede consultar la codificación Wang , descrita en George Boolos & John Burgess & Richard Jeffrey, Computability and Logic (5.ª ed. - 2007): Capítulo 8.1 Codificación Turing Computations , página 88 en adelante.

+1 por la pista de la codificación de Wang. (¿Podría explicar por qué cree que no es un problema real?)
@HansStricker: si entendí bien su preocupación, el problema es que las diferentes definiciones "no formales" de entrada/salida dejan lugar a una "interpretación humana", que es "conceptualmente" insatisfactoria en este contexto. Pero tenemos una forma de "estandarizar" la definición (ver los libros de texto de Kleene, Davis, Hermes).
Creo saber a qué libros de texto te refieres con Kleene y Davis, pero ¿a cuál te refieres con Hermes?
@HansStricker - Hans Hermes , Enumerabilidad, decidibilidad, computabilidad (edición alemana - 1961) - He leído la traducción al italiano.

También puede consultar C. Papadimitriou , Complejidad computacional donde, en mi opinión, las máquinas de Turing se definen sin ambigüedades.

¿Qué quiere decir con "problema conceptual real"? No lo entiendo. Pero dado que Turing Machines puede resolver cualquier problema solucionable, diré que lo hay.

Las Máquinas de Turing (TM) se utilizan en la literatura actual como modelo computacional teórico para medir la complejidad y los requisitos de un problema en el tiempo o el espacio. No esperes ver uno frente a ti. Excepto tal vez aquí . Por lo tanto, no elaboramos mucho sobre los detalles de una MT. Por lo general, una TM tiene una entrada separada, una cinta de salida y varias cintas de trabajo. La solidez de una TM se basa en que una cinta de trabajo puede simular muchas cintas finitas en tiempo polinomial.

Después de probar otros teoremas similares, te das cuenta de que los detalles de una TM no importan. Por ejemplo, dada una fórmula SAT escrita en la cinta de entrada, entonces la instancia si la fórmula es su entrada. Nada que ver con toda la cinta inicial ni con las celdas visitadas ni nada. Es solo la fórmula. Tal vez, la fórmula del SAT convertida a binaria, pero eso es todo.

El lado de la cabeza, el número de estados y cualquier otra información no tiene nada que ver con el tamaño de la entrada.

Entrada y salida de una máquina de Turing
RespuestasAquíPolítica de privacidad1y, 3v