On 20 Sie, 08:43, "Marcin 'Qrczak' Kowalczyk" <q...@k...org.pl>
wrote:
> 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.
Z konsumpcją stałego wejścia też można, z konsumpcją
dowolnego... hmmm nie wyobrażam sobie jakby to mogło
wyglądać.

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

> Czyli zakładam, że przez stan maszyny rozumiesz również zawartość
Nie, chodzi po prostu o dwie wartości: stan maszyny przed i po
wykonaniu
instrukcji. Całej taśmy nie trzeba. Wystarczy szóstka którą
przytoczyłem.
Jeśli pojawią się obok siebie dwie identyczne permutacje szóstek
oznacza
to że maszyna się zapętliła.
> > 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"?
Może na przykładzie.
Głowica przed instrukcją numer X poruszała się w zakresie komórek
<start,end>. W wyniku wykonania instrukcji numer X+1 głowica
wychodzi za dotychczasowy zakres i przesuwa się na komórkę nr end+1.
Zapamiętujemy ten fakt przesunięcia się na end+1. Następnie głowica
wykonuje kolejne instrukcje od <X+2,Y> i pracuje np. w zakresie
<end-10,end+1>,
po czym w instrukcji Y+1 znów rozszerza zakres odwiedzonych komórek end
+2.
Decyzja o tym na jaką komórkę głowica ma się przesunąć jest zawsze
względna komórki bieżącej: o jeden w lewo lub o jeden w prawo,
ewentualnie
w tym samym miejscu. Głowica odwiedziła komórki z przykładowego
zakresu
<end-10,end+1>, więc decyzja wpływająca na kolejne rozszerzenie na end
+2
zależy tylko od tego co się działo na komórkach <end-10,end+1>, czyli
na
11-tu komórkach obok tej o którą się rozszerzyła. Te 11 komórek to
komórki
względne. Ilość możliwych szóstek w instrukcjach wykonanych na
komórkach
względnych jest skończona i w trakcie rozszerzania się maszyny na
coraz
większy zakres musi dojść do ich powtórzenia. Jeśli dojdzie do
powtórzenia
to znaczy że maszyna wpisując okresowe dane w kolejne komórki będzie
w
nieskończoność rozszerzała swój zakres, czyli nigdy się nie zatrzyma.

Przyznam że nie jestem pewien na 100% czy to jest poprawne
rozumowanie.

> Co to znaczy "trywialnie rozszerzać"? Po czym rozpoznasz, że
> rozszerzanie zaczęło być trywialne?
No właśnie po tym, że wpływ na rozszerzenie mogą mieć tylko szóstki
zapamiętane w komórkach które zostały odwiedzone pomiędzy kolejnymi
rozszerzeniami. Szóstek jest skończona ilość, więc cykl szóstek
pomiędzy
rozszerzeniami w końcu się powtórzy. Przy czym liczymy względne adresy
komórek, względem komórki o którą się rozszerzył zakres odwiedzonych
komórek.

Pozdrawiam