On 21 Sie, 11:53, Segmentation Fault <c...@o...eu> wrote:

> > Startowa liczba moze być dowolnie duza, wiec potrzeba nieskoncoznej
> > tasmy lub nieskonczonej liczby stanow.
>
> Tak, taśma nieskończona, skończona liczba stanów i symboli. Do takiej
> maszyny był ten dowód.

Qrczak wyrazil w to watpliosc. A sam nie widze jasnej odpowiedzi.

pozdrawiam
bartekltg

do góry

On 21 Sie, 09:52, "Marcin 'Qrczak' Kowalczyk" <q...@k...org.pl>
wrote:
> On Aug 20, 9:50 pm, Mariusz Marszałkowski <m...@g...com> wrote:
>
> > Myślę że nie trzeba zawartości całej taśmy. Wystarczą dwie
> > wartość z taśmy: z komórki na której jest głowica przed i
> > po wykonaniu instrukcji.
>
> W takim razie nie rozumiem, w jaki sposób chcesz rozstrzygać, że
> maszyna się zapętliła.
>
> > Jeśli pojawią się obok siebie dwie identyczne permutacje szóstek
> > oznacza to że maszyna się zapętliła.
>
> Nie jestem pewien, co masz na myśli przez "permutacje szóstek". W
> każdym razie nie oznacza, bo jeśli zawartość taśmy się zmieniła, to
> następnym razem maszyna może zrobić coś innego.
Pierwszej części jestem pewien że jest poprawna. Szóstka to:
1) stan maszyny przed instrukcją
2) stan maszyny po instrukcji
3) stan komórki przed instrukcją
4) stan komórki po instrukcji
5) pozycja (nr komórki) głowicy przed instrukcją
6) pozycja (nr komórki) glowicy po instrukcji
Szóstka to sześć uporządkowanych liczb całkowitych np. (3,4,4,4,2,1).
Po każdej instrukcji szóstka jest zapisywana w tablicy. Jeśli
po sobie pojawią się dwie identyczne permutacje
szóstek to znaczy że maszyna pętli się.


> Ale po kolejnym rozszerzeniu zakresu maszyna może odwiedzić 12
> komórek, a po następnym 13. Jeśli przez 1000000 iteracji zakres
> komórek odwiedzanych przez maszynę na razie się rozszerza, to skąd
> wiesz, czy będzie się rozszerzał w nieskończoność, czy też maszyna
> kiedyś wpadnie w cykl albo się zatrzyma?
No właśnie z tym drugim przypadkiem jest problem, bo głowica może
odwiedzić wszystkie komórki z zakresu od 1 do N i rozszerzyć się
na N+1. Później tak samo, odwiedzić od 1 do N+1 i rozszerzyć na N+2. W
ten
sposób zakres komórek poprzedzających rozszerzenie jest za każdym
razem inny (większy) i nigdy nie dojdzie do powtórzenia. Powstaje
kłopotoliwe
pytanie: czy trzeba analizować wszystkie szóstki z całego zakresu od 1
do N
poprzedzającego rozszerzenie na N+1? Jeśli maszyna ma skończoną ilość
stanów i jeśli komórka ma skończoną ilość stanów, to po dostatecznym
wydłużeniu zakresu dojdzie do powtórzeń. Ale tego nie widzę jasno,
może
się mylę.

Pozdrawiam

do góry