Kilka tygodni temu pokazałem algorytm który dla
każdego automatu skończonego, a więc także dla
każdej maszyny turinga ze skończoną taśmą,
rozwiązuje problem stopu.

Istnieje wiele algorytmów które rozstrzygają problem
stopu na automacie skończonym, przypomnijmy
jeden algorytm:
1) Wpisujemy A <-- 0
2) Wpisujemy B <-- ilość stanów maszyny
3) Wykonujemy jedną instrukcję automatu skończonego
4) Jeśli automat osiągnął warunek stopu to:
a) TAK
b) zakończ
5) Wpisujemy A <-- A + 1
6) Jeśli A > B to:
a) NIE
b) zkończ
7) Wróć do 3
Dowód poprawności: W wyniku wykonania programu
na automacie skończonym zmienia się jego stan.
W automacie skończonym stan poprzedni determinuje
stan następny. Po wykonaniu większej ilości instrukcji
niż jest stanów, przynajmniej jeden stan pojawił się
dwa razy, a więc doszło do wiecznego zapętlenia.



Ciekawe czy dla każdej maszyny turinga z nieskończoną (jednostronnie
bądź obustronnie) taśmą także istnieje jeden algorytm,
który rozstrzyga czy maszyna zatrzyma się, czy zapętli
w nieskończoność? Program działa dla maszyn turinga które
mają dowolną ale ograniczoną ilość stanów i ilość wartości
w komórce:

Algorytm rozstrzygający problem stopu po każdym wykonaniu
instrukcji zapamiętuje w tablicy szóstkę:
(P_o,P_n,S_o,S_n,V_o,_V_n)
P_o - pozycja głowicy (względem poz. startowej) przed wykonaniem
instrukcji
P_n - pozycja głowicy po wykonaniu instrukcji
S_o - stan maszyny przed wykonaniem instrukcji
S_n - stan maszyny po wykonaniu instrukcji
V_o - wartość w komórce przed wykonaniem instrukcji
V_n - wartość w komórce po wykonaniu instrukcji
Mogą zdarzyć się 3 rzeczy:
1) Podczas symulowania instrukcji w tablicy mogą pojawić się dwie
identyczne permutacje szóstek obok siebie - oznacza to że
algorytm się pętli w nieskończoność.
2) Zakres komórek odwiedzanych przez głowicę poszerzył się
w lewo lub w prawo (tzn głowica ustawiła się na komórce pierwszy
raz), a istnieje zapamiętany identyczny ciąg względnych zmian przed
poprzednim poszerzeniem.
3) Został osiągnięty warunek stopu.

Ze skończoności ilości stanów w komórce i z skończoności ilości
stanów maszyny wynika, że maszyna albo trywialnie się zapętli, albo
zacznie trywialnie rozszerzać zakres zmienionych przez
siebie komórek.


Jeśli algorytm jest poprawny, to pozostał nierozstrzygnięty tylko
ostatni problem, czyli problem stopu maszyny z dowolnymi danymi.

Pozdrawiam