On Aug 19, 9:53 pm, Mariusz Marszałkowski <m...@g...com> wrote:
> 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

Automat skończony ma nie tylko stan, ale i konsumuje wejście. Jeśli
nawet stan się powtórzył, to nie wynika z tego, że automat się
zapętlił, bo na wejściu może być dalej coś innego.

> 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

Czy przez stan maszyny rozumiesz również zawartość taśmy? Maszyna
Turinga ma coś nazywanego stanem (przyjmującym w danej chwili jedną ze
skończenie wielu wartości) i taśmę.

> 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ść.

Czyli zakładam, że przez stan maszyny rozumiesz również zawartość
taśmy, inaczej z powtórzenia szóstki nie wynika zapętlenie, bo na
taśmie może być już coś innego.

> 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.

Nie rozumiem tego sformułowania. Czy do stanu wciąż włączasz zawartość
taśmy? Co to znaczy "identyczny ciąg względnych zmian"?

> 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.

Co to znaczy "trywialnie rozszerzać"? Po czym rozpoznasz, że
rozszerzanie zaczęło być trywialne?