¿Es decidible si un TM alcanza alguna posición en la cinta?

14

Tengo estas preguntas de un antiguo examen que estoy tratando de resolver. Para cada problema, la entrada es una codificación de una máquina de Turing M .

Para un entero c>1 , y los siguientes tres problemas:

  1. ¿Es cierto que para cada entrada x , M no pasa el |x|+c Posición + c cuando se ejecuta en x ?

  2. ¿Es cierto que por cada entrada x , M no pasa el max{|x|c,1} posición cuando se ejecuta en x ?

  3. ¿Es cierto que para cada entrada x , M no pasa la posición (|x|+1)/c cuando se ejecuta en x ?

¿Cuántos problemas son decidibles?

El número de problema (1), en mi opinión, está en si entiendo correctamente, ya que puedo ejecutar todas las entradas en paralelo y detenerme si alguna entrada llegó a esta posición y, al mostrar que no está en R , puedo reducir el complemento de cajero automático . Construyo una máquina de Turing M 'de la siguiente manera: para una entrada y compruebo si y es un historial de cómputo, si es así, entonces M ' funciona correctamente y no se detiene, si no lo es, entonces se detiene.coRERRMyyM

Para (3), creo que es decidible ya que para son todas las máquinas de Turing que siempre permanecen en la primera celda de la banda, ya que para una cadena de un carácter puede pasar la primera celda, por lo que necesito simular todas las cadenas de longitud 1 para | Q | + 1 pasos (¿Es esto correcto?), Y vea si estoy usando solo la primera celda en todos ellos.c2|Q|+1

Realmente no sé qué hacer con (2).

Jozef
fuente
1) ¿Asumes una cinta infinita unilateral? 2) ¿Qué es el cajero automático?
Raphael
1) Sí, 2) El problema de aceptación.
Jozef

Respuestas:

9

Cualquier situación que pregunte si una máquina de Turing está confinada a una sección finita de la cinta (digamos de longitud ) en una entrada dada es decidible.n

El argumento funciona de la siguiente manera. Considere la máquina de Turing, la cinta y la posición de la máquina de Turing en la cinta. Todos juntos tienen un número finito de configuraciones. Para ser específicos, solo hay posibles configuraciones. Γ es el conjunto de símbolos de cinta y Q es el conjunto de estados. Continuaré usando la palabra "configuración" para describir el estado de la Máquina de Turing combinado con el estado de la cinta y su posición en la cinta para el resto de esta respuesta, pero ese no es el vocabulario estándar.t=n|Γ|n|Q|ΓQ

Ejecute la máquina y realice un seguimiento de todas sus configuraciones pasadas. Si alguna vez va más allá del punto , devuelve "sí,n pasa a la posición n ". De lo contrario, la máquina está en algún lugar entre 0 y n . Si la máquina alguna vez repite una configuración (su estado, los símbolos en la cinta y su posición en la cinta son idénticos a lo que eran antes), devuelva "no, M nunca pasa la posición n ".MnnMn

Por el principio de pidgeonhole, esto tiene que suceder en no más de pasos. Entonces, todo lo anterior es decidible; después de como máximo t + 1 pasos simulados, obtienes una respuesta.t+1t+1

Una nota rápida sobre por qué funciona esto: cuando la máquina, la cinta y su posición en la cinta se repiten, debe haber una secuencia de configuraciones entre estas repeticiones. Esta secuencia volverá a ocurrir, lo que lleva a la misma configuración una vez más: la máquina está en un bucle infinito. Esto se debe a que estamos realizando un seguimiento de todos los aspectos de la Máquina Turing; nada fuera de la configuración puede tener un impacto en lo que sucedió. Entonces, cuando una configuración se repite, se repetirá nuevamente, con una serie idéntica de configuraciones intermedias.

Por lo tanto, limitar la cinta a una parte finita de la cadena es decidible. Por lo tanto, al iterar sobre todas las cadenas de entrada posibles, el problema está en el de las tres preguntas. Es posible que ya se haya dado cuenta de esto (entre sus ideas para 1 y 3 y la respuesta de Ran G para 2 parece resuelto por completo de todos modos) pero pensé que, sin embargo, vale la pena publicarlo.coRE

SamM
fuente
"Si la máquina alguna vez repite una configuración, [...] devuelva 'no'", eso está mal. Una máquina no determinista puede ejecutar un bucle un par de veces y luego seguir adelante.
Raphael
1
Estamos hablando de máquinas de turing aquí que no se supone que sean no deterministas. Si no fuera determinista, simule la versión determinista.
SamM
Buena explicación Vea también la primera versión de mi respuesta (que revisé una vez que me di cuenta de que el OP no lo había preguntado ...)
Ran G.
@Sam: Funciona al revés: a menos que se asuma lo contrario, una máquina de Turing puede no ser determinista. ¿Qué es una "versión determinista"? Si se refiere a un despliegue completo de opciones, una configuración repetida pierde significado, ya que pueden suceder en diferentes ramas.
Rafael
2
@Raphael la forma estándar de hacer esto es un gráfico de configuración: los vértices son las mismas configuraciones que Sam definió, y hay un borde dirigido de la configuración A a B si el NTM puede moverse de A a B en un solo paso. El gráfico es finito y si la máquina se detiene es una simple pregunta de alcance del gráfico. Esto también muestra que es un subconjunto de D T I M E ( 2 O ( s ) )NSPACE(s)DTIME(2O(s))
Sasho Nikolov
4

(2) es muy similar a (3) y el mismo razonamiento que tenía para (3) también se aplica aquí: tenga en cuenta que las máquinas que en L2 tienen una propiedad extraña: no leen toda la entrada (nunca alcanzan últimos bits.) Y esto es cierto para cada entrada.c

Ok, ahora consideremos solo entradas de hasta . Para cada uno de ellos, solo hay dos opciones: la máquina gira / se detiene sin mover la cabeza, o mueve la cabeza. Si mueve la cabeza en alguna x (con | x |c ), esa máquina no está en L 2 debido a esa entrada x . De lo contrario, afirmo que la máquina está en L 2 . Como nunca mueve la cabeza, ¡no tiene idea de cuál es el tamaño de la entrada! esto significa que se comporta igual para todas las entradas de longitud | x | > c . Por lo tanto, L 2 es decidible.cx|x|cL2xL2|x|>cL2

Sonó.
fuente
¿Cómo se contabilizan las máquinas no deterministas?
Raphael
No consideré las MNA, pero debería ser lo mismo. Para todas las palabras de longitud hasta el número de configuraciones en que puede estar el NTM sin mover la cabeza es finito. c
Ran G.
Sí, pero tu argumento se rompe. No puede determinar en tiempo finito (por simple simulación) si una NTM abandona una posición determinada.
Raphael
@ Raphael, ¿por qué no? ¿no puedes simular todo el árbol de configuraciones (de profundidad ) en un tiempo finito e x p ( | x | ) ? |x|exp(|x|)
Ran G.
¿Por qué la profundidad ¿bastar? El | Q | Tendría más sentido. Para entonces, la simulación ha encontrado una rama donde M abandona la primera posición, si hay alguna. |x||Q|M
Raphael