O conjunto de máquinas de Turing que para em no máximo 50 etapas em todas as entradas é decidível?

Deixe . Preciso decidir se F é decidível ou recursivamente enumerável. Eu acho que é decidível, mas não sei como provar.$F = \{⟨M⟩:\text{M is a TM which stops for every input in at most 50 steps}\}$

Meus pensamentos

Esta parte dos "50 passos" imediatamente transforma o sinal R para mim. Se fosse para informações específicas, seria decidível. No entanto, aqui está para cada entrada. Verificá-lo para infinitas entradas me faz pensar que o problema é co-RE , ou seja , seu complemento é aceitável.

Talvez eu possa verificar as configurações e ver que todas as configurações após 50 etapas não levam ao estado de aceitação - como faço isso?

$N$$N \geqslant 1$

Como swegi observa em uma resposta anterior, se a máquina parar após no máximo etapas, somente as células na fita são significativas. Basta simular a máquina em todas as seqüências de entrada do formato , das quais existe um número finito.$N$$0,1,\ldots,N-1$$M$$x \in \Sigma^N$

• Se alguma dessas simulações falhar em entrar em um estado de parada pelotransição, isso indica que qualquer sequência de entrada começando com é aquela para a qual a máquina não para nas primeiras etapas.$N^{\text{th}}\:\!$$x$$N$
• Se todas essas simulações forem interrompidas pelotransição, então pára dentro de etapas em todas as entradas de qualquer comprimento (das quais a subcadeia de comprimento é tudo em que atua).$N^{\text{th}}\:\!$N $M$$N$$N$

Se parar em não mais que 50 passos, as posições que M pode alcançar na fita normalmente infinita são limitadas. Assim, a fita infinita pode ser simulada por uma fita finita. Isso significa que a fita pode ser simulada por um autômato finito. Daqui resulta que uma máquina de turing M que para em não mais do que 50 etapas é bimimilar de algum autômato finito M ' .$M$$M$$M$$M'$

Seja o conjunto de estados de M , F ⊂ Q o conjunto de estados aceitantes e Γ seja o alfabeto. Em seguida, vamos construir o conjunto de estados Q ' de M ' da seguinte forma: Q ' = { ⟨ n , q , s , p , um $Q$$M$$F \subset Q$$\Gamma$$Q'$$M'$ onde p é a posição da cabeça de leitura / gravação acima da fita. Podemos restringir a posição para { - 50 , . . . , 50 } porque o número de etapas de computação permitidas limita o número de posições alcançáveis.$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\}$

Tendo um estado do autómato finito M ' , em seguida, significa que estamos em estado Q do autómato original, com s sobre a fita na posição p , onde também a cabeça de leitura / gravação está posicionado , após a n- ésima etapa da computação. O estado é um um aceitar se um ≡ t r u e .$\langle n, q, s, p, a\rangle$$M'$$q$$s$$p$$n$$a \equiv true$

Transformar a relação de transição de uma máquina de turing de concreto é um pouco mais trabalhoso, mas não é necessário para a pergunta original, pois basta mostrar que o espaço de estados é finito (e, portanto, podemos apenas testar cada entrada com um comprimento máximo de 50 símbolos em cada um desses autômatos). A ideia é a construção de uma nova relação de transição que vai de um estado para um estado ⟨ n + 1 , Q ' , s ' , p ' , um ' ⟩ no $\langle n, q, s, p, a \rangle$$\langle n+1, q', s', p', a'\rangle$$n$-ésima etapa sse a transição de computação estava na relação de transição inicial.$\langle q, s, p\rangle \rightarrow \langle q', s', p'\rangle$