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

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.$\text {coRE} \smallsetminus \text R$$\text R$$M'$$y$$y$$M'$

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.$c \geqslant 2$$|Q|+1$

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

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|\Gamma|^n|Q|$$\Gamma$$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 ".$M$$n$$n$$M$$n$

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+1$$t+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.$\text{coRE}$

(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 $L_2$ 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.$c$$x$$|x|\le c$$L_2$$x$$L_2$$|x|>c$$L_2$