JFiZO - Lista 7

Nie, nie jest rozstrzygalny.
Dowód będzie poprzez pokazanie redukcji tego problemu do znanego nam problemu stopu maszyny Turinga. Innymi słowy, dostając maszynę Turinga T, zbudujemy maszynę skanującą S, która będzie symulować T, czyli wykonywać na taśmie te same operacje, w szczególności będzie zachodzić równoważność:
T się zatrzymuje \Leftrightarrow S się zatrzymuje.
To będzie bajka o żuczku z Altzheimerem.

Niech T = \langle \Sigma, Q, q_0, q_F, \delta \rangle. Konstruujemy S = \Sigma \cup \{x, b\}, Q \cup Q \times Sigma \cup Q \times \Sigma \times \Sigma \times Pewien\_Zbior\_Operacji, q_0, q_F, \delta' \rangle. Nie będę dokładnie opisywał delty, tylko opiszę jak to działa.

• Symbol „x” będzie oznaczał miejsce, od którego zaczęliśmy robić sobie spacer. Podczas ruszania się w prawo nie będzie nam to potrzebne, potem jednak niezmiernie.
• Symbol „b” będę nazywał „małym blankiem”, czyli czymś, co w T powinno być blankiem, ale u nas nie może być z racji tego, że będziemy masę razy łazić nadmiarowo. Także ilekroć będziemy pisać \delta(q, B, \ldots) \Rightarrow \delta'(q', B, costam), to milcząco dodajemy też instrukcję \delta'(q', b, costam)
• Stany dzielą się, jak widać, na trzy grupy: pierwsza z nich jest dość intuicyjna: to jest stan w maszynie T, w którym się „znajdujemy”. Możemy więc dość łatwo opisać tę prostszą część delty prim: \delta(q, a, q', a', \to) \Rightarrow \delta'(q, a, q', a')
• W momencie jednak, gdy mamy instrukcję \delta(q, a, q', a', \gets), musimy wykonać szereg skomplikowanych rzeczy:
  • \delta'(q, a, (q',a'), x), czyli napisać „x” w miejscu gdzie jesteśmy, i przejść do stanu, który pamięta co należy wpisać na miejsce tego iksa.
  • przejść w tym stanie (q', a') do końca, blanka B nadpisać małym blankiem i przejść, jak nam każą, na początek
  • równie gładko ominąć alfę
  • Następnie, używając kolejnego iksa (drugiego), posuwać się z nim powoli w prawo, czyli powtarzać następujące czynności:
    • (1) zapamiętaj co masz pod sobą (a' ') , nasraj tam iksem i przejdź na następne pole
    • Jeżeli trafiłeś na iksa to znaczy, że doszedłeś tam, gdzie powinieneś być. Wówczas:
      • nadpisz tego iksa literką, którą zrobiłaby to T, czyli a'
      • zrób pętelkę do iksa drugiego, nadpisz go tym, co tam powinno być, czyli a' ' (zapamiętaj też jaką operację wykonujesz!)
      • przejdź do normalnego wykonywania, czyli do stanu q' i zakończ pętlę (1)
    • jeżeli nie trafiłeś na iksa, to
      • zrób pełną pętlę z powrotem do tego przed chwilą nasranego (znowu, w stanie musisz zawrzeć informację o tym co się dzieje)
      • nadpisz go tym, co tam powinno być (czyli a' ')
      • przejdź do następnej literki i w kółko macieju (1)
  • po wykonaniu tych wszystkich kroków, poza naprodukowaniem sobie miliardów sztucznych blanków, udało nam się przesunąć jedno pole w lewo, innymi słowy zasymulować jeden krok maszyny T.
    
• Nietrudno zauważyć, że w momencie, w którym jesteśmy w stanie postaci q \in Q, to na taśmie nie ma żadnego iksa i, gdybyśmy utożsamili małe i duże blanki, jesteśmy w pewnym stanie pędzącej maszyny T. Innymi słowy, jeżeli T się zatrzyma, my też nie będziemy mieli co zrobić. Jeżeli nie - będziemy cały czas ją symulować. To dowodzi, że problem stopu maszyn skanujących jest nierozstrzygalny.