Czy decydujący jest zestaw maszyn Turinga, który zatrzymuje się co najwyżej 50 kroków na wszystkich wejściach?

Niech . Muszę zdecydować, czy F jest rozstrzygalne, czy rekurencyjnie wyliczalne. Myślę, że jest to rozstrzygalne, ale nie wiem, jak to udowodnić.$F = \{⟨M⟩:\text{M is a TM which stops for every input in at most 50 steps}\}$

Moje myśli

Ta część „50 kroków” natychmiast zmienia dla mnie znak R. Gdyby to było dla konkretnych danych wejściowych, byłoby rozstrzygalne. Jednak tutaj jest dla każdego wejścia. Sprawdzanie go pod kątem nieskończonych danych wejściowych sprawia, że ​​myślę, że problem dotyczy co-RE , tj. Jego dopełnienie jest dopuszczalne.

Być może mogę sprawdzić konfiguracje i zobaczyć, że wszystkie konfiguracje po 50 krokach nie prowadzą do zaakceptowania stanu - jak to zrobić?

Rozważmy bardziej ogólny problem maszyn, które zatrzymują się po co najwyżej krokach, dla niektórych . (Poniżej przedstawiono znaczne uproszczenie poprzedniej wersji tej odpowiedzi, ale w rzeczywistości jest równoważne).$N$$N \geqslant 1$

Jak zauważa swegi we wcześniejszej odpowiedzi, jeśli maszyna zatrzymuje się po co najwyżej $N$ krokach, znaczące są tylko komórki $0,1,\ldots,N-1$ na taśmie. Następnie wystarczy zasymulować maszynę $M$ na wszystkich ciągach wejściowych postaci $x \in \Sigma^N$ , których liczba jest skończona.

• Jeśli którakolwiek z tych symulacji nie wejdzie w stan zatrzymania przez $N^{\text{th}}\:\!$przejście oznacza, że ​​dowolny ciąg wejściowy rozpoczynający się od $x$ to taki, dla którego maszyna nie zatrzymuje się w ciągu pierwszych $N$ kroków.
• Jeśli wszystkie te symulacje zostaną zatrzymane przezprzejście, następnie zatrzymuje się w obrębie kroków na wszystkich wejściach dowolnej długości (na których podciąg długości jest wszystkim, na co kiedykolwiek działa).$N^{\text{th}}\:\!$$M$$N$$N$

Jeśli zatrzymuje się w nie więcej niż 50 krokach, pozycje M, które może osiągnąć na normalnie nieskończonej taśmie, są ograniczone. Zatem taśma nieskończona może być symulowana przez taśmę skończoną. Oznacza to, że taśma może być symulowana przez automat skończony. Wynika z tego, że maszyna Turinga M, która zatrzymuje się w nie więcej niż 50 krokach, jest podobna do jakiegoś skończonego automatu M ' .$M$$M$$M$$M'$

Niech będzie zbiorem stanów M , F ⊂ Q zbiorem stanów akceptujących i Γ alfabetem. Następnie utworzenia zestawu stanów Q ' o M ' w następujący sposób: Q ' = { ⟨ n , q , Ś , s , $Q$$M$$F \subset Q$$\Gamma$$Q'$$M'$ gdzie p jest pozycją głowicy odczytu / zapisu nad taśmą. Możemy ograniczyć pozycję { - 50 , . . . , 50 }, ponieważ liczba dozwolonych kroków obliczeniowych ogranicza liczbę osiągalnych pozycji.$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\}$

Uwzględniając stan skończonego automatu M " to znaczy, że są w stanie Q pierwotnego automat z S na taśmie w położeniu p w którym również zapisu / odczytu głowica jest umieszczona , po n-tym kroku obliczeniowym. Stan jest przyjmowanie jednej czy z ≡ t r u E .$\langle n, q, s, p, a\rangle$$M'$$q$$s$$p$$n$$a \equiv true$

Przekształcenie relacji przejścia betonowej maszyny Turinga jest nieco więcej pracy, ale nie jest konieczne w pierwotnym pytaniu, ponieważ wystarczy pokazać, że przestrzeń stanu jest skończona (a zatem możemy po prostu przetestować każde wejście o długości co najwyżej 50 symbole na każdym takim automacie). Chodzi o to, aby zbudować nowy związek przejściowy, który przechodzi ze stanu do stanu ⟨ n + 1 , Q ' , s ' , s " , a " ⟩ w w $\langle n, q, s, p, a \rangle$$\langle n+1, q', s', p', a'\rangle$$n$-tym obliczania etapu iff przejścia było w oryginalnym związku przejściowego.$\langle q, s, p\rangle \rightarrow \langle q', s', p'\rangle$