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

do góry

On 19 Sie, 21:53, Mariusz Marszałkowski <m...@g...com> wrote:

> Istnieje wiele algorytmów które rozstrzygają problem
> stopu na automacie skończonym, przypomnijmy
> jeden algorytm:

Niestety bezużyteczny w praktyce ze względu na nieredukowalność
obliczeniową wielu automatów.
Chodzi o to, że aby ten problem rozstrzygnąć, musisz (zgodnie ze
opisanymi metodami), *wykonać* badany algorytm. To jest zwykły
emulator.
Nie ma w tych metodach żadnego "skrótu", który by oszacował wynik
szybciej, niż trwa wykonanie badanego automatu.

Przykład: powiedzmy, że mamy komputer z 1GB RAMu i program, który na
całej tej pamięci robi licznik na wszystkich dostępnych bitach,
zwiększany ze średnią czybkością 1GHz - to taka pierwsza lekcja
asemblera. Ten program musi się albo zapętlić albo zatrzymać, ale jego
wykonanie trwa:

(2**(8*(2**30)))/(10**9) sekund,

czyli dłużej, niż będzie istniał cały wszechświat.

Jeżeli Twój algorytm nie potrafi tego rozstrzygnąć szybciej, niż przez
obserwację tego nudnego procesu, to jest kompletnie bezużyteczny.

--
Maciej Sobczak * http://www.inspirel.com

do góry

On 19 Sie, 23:22, Maciej Sobczak <s...@g...com> wrote:
> On 19 Sie, 21:53, Mariusz Marszałkowski <m...@g...com> wrote:
>
> > Istnieje wiele algorytmów które rozstrzygają problem
> > stopu na automacie skończonym, przypomnijmy
> > jeden algorytm:
>
> Niestety bezużyteczny w praktyce ze względu na nieredukowalność
> obliczeniową wielu automatów.
No niestety. Tylko mała radość że to teoretycznie jest możliwe, albo
dla bardzo małych automatów.

Pozdrawiam

do góry

W dniu 2010-08-20 04:15, Mariusz Marszałkowski pisze:
> On 19 Sie, 23:22, Maciej Sobczak<s...@g...com> wrote:
>> On 19 Sie, 21:53, Mariusz Marszałkowski<m...@g...com> wrote:
>>
>>> Istnieje wiele algorytmów które rozstrzygają problem
>>> stopu na automacie skończonym, przypomnijmy
>>> jeden algorytm:
>>
>> Niestety bezużyteczny w praktyce ze względu na nieredukowalność
>> obliczeniową wielu automatów.
> No niestety. Tylko mała radość że to teoretycznie jest możliwe, albo
> dla bardzo małych automatów.

Dla "bardzo malych automatow" zawsze bylo mozliwe praktyczne
rozstrzygniecie, w najgorszym wypadku przez 'brutal-force'.

Ale to z matematyczną stroną algorytmiki juz nie ma nic wspolnego.

Nie wiem czy istnieje definicja "bardzo małego automatu". Byla by
podobna do kwantyfikatora "prawie wszystkie" ????

;)

do góry

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?

do góry

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

do góry

On 20 Sie, 10:50, Segmentation Fault <c...@o...eu> wrote:

> 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 :(

http://pl.wikipedia.org/wiki/Problem_Collatza


> anyway,  maszyna Turinga która go liczy ma skończony alfabet i skończoną
> liczbę stanów.

Startowa liczba moze być dowolnie duza, wiec potrzeba nieskoncoznej
tasmy lub nieskonczonej liczby stanow.

pozdrawiam
bartekltg

do góry

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

do góry

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.

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

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?

do góry

On 08/20/2010 03:08 PM, bartekltg wrote:
> On 20 Sie, 10:50, Segmentation Fault <c...@o...eu> wrote:
>
>> 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 :(
>
> http://pl.wikipedia.org/wiki/Problem_Collatza
>
>
>> anyway, maszyna Turinga która go liczy ma skończony alfabet i skończoną
>> liczbę stanów.
>
> 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.

do góry