Czy jest rozstrzygalne, czy TM osiągnie jakąś pozycję na taśmie?

Mam te pytania ze starego egzaminu, który próbuję rozwiązać. Dla każdego problemu wejście jest kodowanie pewnej maszyny Turingowi .$M$

Dla liczby całkowitej i następujących trzech problemów:$c>1$

1. Czy to prawda, że ​​dla każdego wejścia , M nie przechodzi przez pozycję podczas pracy na ?$x$$|x|+c$$x$

2. Czy to prawda, że ​​dla każdego wejścia , M nie przechodzi przez pozycję podczas pracy na x ?$x$$\max \{|x|-c,1 \}$$x$

3. Czy to prawda, że ​​dla każdego wejścia $x$ , M nie przechodzi w pozycję $(|x|+1)/c$ podczas pracy na $x$ ?

Ile problemów można rozstrzygnąć?

Moim zdaniem numer problemu (1) znajduje się w $\text {coRE} \smallsetminus \text R$ jeśli dobrze rozumiem, ponieważ mogę uruchomić wszystkie dane wejściowe równolegle i zatrzymać się, jeśli niektóre dane wejściowe osiągną tę pozycję, i pokazując, że to nie jest w $\text R$ Mogę zredukować do tego dopełnienie Atm . Skonstruować maszynę Turinga $M'$ w następujący sposób: na wejście $y$ sprawdzić, jeśli $y$ to historia obliczeń, jeśli tak jest, to $M'$ prawo jazdy i nie zatrzyma się, jeśli nie jest, to zatrzyma.

W przypadku (3) uważam, że jest to rozstrzygalne, ponieważ w przypadku $c \geqslant 2$ wszystkie maszyny Turinga zawsze pozostają na pierwszej komórce paska, ponieważ dla ciągu jednego znaku może przejść przez pierwszą komórkę, więc ja muszę zasymulować wszystkie ciągi długości 1 dla kroków $|Q|+1$ (Czy to poprawne?) i sprawdzić, czy używam tylko pierwszej komórki we wszystkich.

Naprawdę nie wiem, co zrobić z (2).

Każda sytuacja, która pyta, czy maszyna Turinga ogranicza się do skończonej części taśmy (powiedzmy o długości ) na danym wejściu, jest rozstrzygalna.$n$

Argument działa w następujący sposób. Rozważ maszynę Turinga, taśmę i położenie maszyny Turinga na taśmie. Wszystkie razem mają skończoną liczbę konfiguracji. Aby być konkretnym, są tylkomożliwe konfiguracje. jest zbiorem symboli taśmy, a jest zbiorem stanów. Nadal będę używać słowa „konfiguracja”, aby opisać stan Maszyny Turinga w połączeniu ze stanem taśmy i jej pozycją na taśmie do końca tej odpowiedzi, ale to nie jest standardowe słownictwo.$t = n|\Gamma|^n|Q|$$\Gamma$$Q$

Uruchom maszynę, śledząc wszystkie jej wcześniejsze konfiguracje. Jeśli kiedykolwiek przekroczy punkt , zwróć „tak, mija pozycję ”. W przeciwnym razie maszyna znajduje się gdzieś pomiędzy 0 a . Jeśli maszyna kiedykolwiek powtórzy konfigurację - jej stan, symbole na taśmie i jej położenie na taśmie są identyczne z poprzednimi - zwróć „nie, nigdy nie przechodzi w pozycję ”.$n$$M$$n$$n$$M$$n$

Zgodnie z zasadą pidgeonhole musi się to odbywać nie więcej niż w krokach . Wszystko powyższe jest rozstrzygalne; po co najwyżej symulowanych krokach otrzymasz odpowiedź.$t+1$$t+1$

Krótka uwaga na temat tego, dlaczego to działa: kiedy urządzenie, taśma i jej położenie na taśmie powtarzają się, musi istnieć sekwencja konfiguracji między tymi powtórzeniami. Ta sekwencja powtórzy się, prowadząc jeszcze raz do tej samej konfiguracji - maszyna znajduje się w nieskończonej pętli. Jest tak, ponieważ śledzimy każdy aspekt Maszyny Turinga; nic poza konfiguracją nie może mieć wpływu na to, co się stało. Tak więc, gdy konfiguracja się powtarza, powtórzy się ponownie, z identyczną serią konfiguracji pomiędzy.

Zatem ograniczenie taśmy do skończonej części sznurka jest rozstrzygalne. Dlatego iterując wszystkie możliwe ciągi wejściowe, problem leży w dla wszystkich trzech pytań. Być może już zdałeś sobie z tego sprawę (między twoimi pomysłami na 1 i 3 a odpowiedzią Ran G na 2 i tak wydaje się całkowicie rozwiązany), ale pomyślałem, że mimo wszystko warto to opublikować.$\text{coRE}$

(2) jest bardzo podobny do (3) i dotyczy to również tego samego rozumowania, które miałeś dla (3): zauważ, że maszyny, które w mają dziwną właściwość - nie czytają całego wejścia (nigdy nie osiągają tego ostatnie bity c ). I dotyczy to każdego wejścia.$L_2$$c$

Ok, teraz rozważmy tylko dane wejściowe do długości . Dla każdego z nich są tylko dwie opcje: maszyna zapętla / zatrzymuje się bez poruszania głową lub porusza głową. Jeśli porusza głową o jakieś x (z | x | ≤ c ), to maszyna nie znajduje się w L 2 z powodu tego wejścia x . W przeciwnym razie twierdzę, że maszyna jest w L 2 . Ponieważ nigdy nie porusza głową - nie ma pojęcia, jaki jest rozmiar wejścia! oznacza to, że zachowuje się tak samo dla wszystkich danych wejściowych długości | x | > c . Dlatego też, L 2 jest rozstrzygalne.$c$$x$$|x|\le c$$L_2$$x$$L_2$$|x|>c$$L_2$