¿El conjunto de máquinas de Turing que se detiene en un máximo de 50 pasos en todas las entradas es decidible?

Deje . Necesito decidir si F es decidible o recursivamente enumerable. Creo que es decidible, pero no sé cómo demostrarlo.$F = \{⟨M⟩:\text{M is a TM which stops for every input in at most 50 steps}\}$

Mis pensamientos

Esta parte de "50 pasos" convierte inmediatamente el signo R para mí. Si fuera por una entrada específica, sería decidible. Sin embargo, aquí está para cada entrada. Verificarlo por entradas infinitas me hace pensar que el problema es co-RE , es decir , su complemento es aceptable.

Tal vez, puedo verificar las configuraciones y ver que todas las configuraciones después de 50 pasos no conducen a aceptar el estado. ¿Cómo hago eso?

Consideremos el problema más general de las máquinas que se detienen después de, como máximo, pasos, para algunos . (La siguiente es una simplificación sustancial de una versión anterior de esta respuesta, pero es efectivamente equivalente).$N$$N \geqslant 1$

Como señala swegi en una respuesta anterior, si la máquina se detiene después de como máximo $N$ pasos, entonces solo las celdas $0,1,\ldots,N-1$ en la cinta son significativas. Entonces es suficiente simular la máquina $M$ en todas las cadenas de entrada de la forma $x \in \Sigma^N$ , de las cuales hay un número finito.

• Si alguna de estas simulaciones no puede entrar en un estado de detención mediante $N^{\text{th}}\:\!$transición, esto indica que cualquier cadena de entrada que comience con $x$ es una para la cual la máquina no se detiene dentro de los primeros $N$ pasos.
• Si todas estas simulaciones se detienen contransición, entonces detiene dentro de pasos en todas las entradas de cualquier longitud (de las cuales la subcadena de longitud es en todo lo que actúa).$N^{\text{th}}\:\!$$M$$N$$N$

Si detiene en no más de 50 pasos, las posiciones que puede alcanzar en la cinta normalmente infinita son limitadas. Así, la cinta infinita puede ser simulada por una finita. Esto significa que la cinta puede ser simulada por un autómata finito. De ello se deduce que una máquina de turing que se detiene en no más de 50 pasos es similar a un autómata finito .M M M $M$$M$$M$$M'$

Sea el conjunto de estados de , el conjunto de estados de aceptación y el alfabeto. Luego construimos el conjunto de estados de siguiente manera: donde es la posición del cabezal de lectura / escritura sobre la cinta. Podemos restringir la posición a porque el número de pasos informáticos permitidos limita el número de posiciones alcanzables.M F ⊂ Q Γ Q ' M ' Q ' = { ⟨ n , q , s , p , un $Q$$M$$F \subset Q$$\Gamma$$Q'$$M'$p { - 50 , . . . , 50 $Q' = \{ \langle n, q, s, p, a\rangle \, | n \in \{0,...,50\} \, q \in Q, s \in \Gamma, p \in \{-50,...,50\}, a \equiv q \in F\}$$p$$\{-50,...,50\}$

Tener un estado del autómata finito significa que estamos en el estado del autómata original, con en la cinta en la posición donde también el cabezal de lectura / escritura está colocado, después de que el -ésimo paso de cálculo. El estado es aceptable si .M ' q s p n un ≡ t r u $\langle n, q, s, p, a\rangle$$M'$$q$$s$$p$$n$$a \equiv true$

Transformar la relación de transición de una máquina de hormigón de turing es un poco más de trabajo, pero no es necesario para la pregunta original, ya que es suficiente para mostrar que el espacio de estado es finito (y, por lo tanto, solo podemos probar cada entrada con una longitud de 50 como máximo) símbolos en cada autómata). La idea es construir una nueva relación de transición que vaya desde un estado a un estado en el -ésimo de computación paso si y sólo si la transición estaba en la relación de transición inicial.⟨ n + 1 , q ' , s ' , p ' , una ' ⟩ n ⟨ q , s , p ⟩ → ⟨ q ' , s ' , p '$\langle n, q, s, p, a \rangle$$\langle n+1, q', s', p', a'\rangle$$n$$\langle q, s, p\rangle \rightarrow \langle q', s', p'\rangle$