On 08/19/2010 09:53 PM, Mariusz Marszałkowski wrote:
> 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.

Możesz podesłać coś na temat maszyny Turinga o nieskończonej ilości
stanów i nieskończonej ilości symboli ?

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

Hm, jest taki program na tablicy BUW:
http://www.mimuw.edu.pl/rozne/stare/tablica.html

niestety nie udało mi się wygalować zdjęcia gdzie jest czytelny :(

anyway, maszyna Turinga która go liczy ma skończony alfabet i skończoną
liczbę stanów. Ten program - zatrzyma się ?