eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingAlgorytm do rozstrzygania problemu stopu dowolnej MT
Ilość wypowiedzi w tym wątku: 12

  • 1. Data: 2010-08-19 19:53:55
    Temat: Algorytm do rozstrzygania problemu stopu dowolnej MT
    Od: Mariusz Marszałkowski <m...@g...com>

    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


  • 2. Data: 2010-08-19 21:22:25
    Temat: Re: Algorytm do rozstrzygania problemu stopu dowolnej MT
    Od: Maciej Sobczak <s...@g...com>

    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


  • 3. Data: 2010-08-20 02:15:19
    Temat: Re: Algorytm do rozstrzygania problemu stopu dowolnej MT
    Od: Mariusz Marszałkowski <m...@g...com>

    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


  • 4. Data: 2010-08-20 04:56:04
    Temat: Re: Algorytm do rozstrzygania problemu stopu dowolnej MT
    Od: Jacek Czerwinski <...@...z.pl>

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

    ;)


  • 5. Data: 2010-08-20 06:43:55
    Temat: Re: Algorytm do rozstrzygania problemu stopu dowolnej MT
    Od: "Marcin 'Qrczak' Kowalczyk" <q...@k...org.pl>

    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?


  • 6. Data: 2010-08-20 08:50:14
    Temat: Re: Algorytm do rozstrzygania problemu stopu dowolnej MT
    Od: Segmentation Fault <c...@o...eu>

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




  • 7. Data: 2010-08-20 13:08:45
    Temat: Re: Algorytm do rozstrzygania problemu stopu dowolnej MT
    Od: bartekltg <b...@g...com>

    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


  • 8. Data: 2010-08-20 19:50:46
    Temat: Re: Algorytm do rozstrzygania problemu stopu dowolnej MT
    Od: Mariusz Marszałkowski <m...@g...com>

    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




  • 9. Data: 2010-08-21 07:52:57
    Temat: Re: Algorytm do rozstrzygania problemu stopu dowolnej MT
    Od: "Marcin 'Qrczak' Kowalczyk" <q...@k...org.pl>

    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?


  • 10. Data: 2010-08-21 09:53:09
    Temat: Re: Algorytm do rozstrzygania problemu stopu dowolnej MT
    Od: Segmentation Fault <c...@o...eu>

    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.

strony : [ 1 ] . 2


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: