eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingAlgorytm do rozstrzygania problemu stopu dowolnej MTRe: Algorytm do rozstrzygania problemu stopu dowolnej MT
  • Path: news-archive.icm.edu.pl!news.icm.edu.pl!news.nask.pl!news.nask.org.pl!news.uni-
    stuttgart.de!news.belwue.de!kanaga.switch.ch!switch.ch!feeder.news-service.com!
    feeder.news-service.com!postnews.google.com!w30g2000yqw.googlegroups.com!not-fo
    r-mail
    From: "Marcin 'Qrczak' Kowalczyk" <q...@k...org.pl>
    Newsgroups: pl.comp.programming
    Subject: Re: Algorytm do rozstrzygania problemu stopu dowolnej MT
    Date: Sat, 21 Aug 2010 00:52:57 -0700 (PDT)
    Organization: http://groups.google.com
    Lines: 37
    Message-ID: <c...@w...googlegroups.com>
    References: <7...@y...googlegroups.com>
    <b...@t...googlegroups.com>
    <6...@d...googlegroups.com>
    NNTP-Posting-Host: 83.7.204.215
    Mime-Version: 1.0
    Content-Type: text/plain; charset=ISO-8859-2
    Content-Transfer-Encoding: quoted-printable
    X-Trace: posting.google.com 1282377177 19320 127.0.0.1 (21 Aug 2010 07:52:57 GMT)
    X-Complaints-To: g...@g...com
    NNTP-Posting-Date: Sat, 21 Aug 2010 07:52:57 +0000 (UTC)
    Complaints-To: g...@g...com
    Injection-Info: w30g2000yqw.googlegroups.com; posting-host=83.7.204.215;
    posting-account=Y4cAXQoAAAAv8UBiA5Li4Y_naLKJKxAx
    User-Agent: G2/1.0
    X-HTTP-UserAgent: Mozilla/5.0 (X11; U; Linux x86_64; en-US) AppleWebKit/534.3 (KHTML,
    like Gecko) Ubuntu/10.04 Chromium/6.0.472.36 Chrome/6.0.472.36
    Safari/534.3,gzip(gfe)
    Xref: news-archive.icm.edu.pl pl.comp.programming:186625
    [ ukryj nagłówki ]

    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?

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

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: