eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingAlgorytm do rozstrzygania problemu stopu dowolnej MTRe: Algorytm do rozstrzygania problemu stopu dowolnej MT
  • Data: 2010-08-21 14:40:27
    Temat: Re: Algorytm do rozstrzygania problemu stopu dowolnej MT
    Od: Mariusz Marszałkowski <m...@g...com> szukaj wiadomości tego autora
    [ pokaż wszystkie nagłówki ]

    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

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj

Najnowsze wątki z tej grupy


Najnowsze wątki

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: