Czy maszyna, która nigdy się nie zatrzymuje, zawsze pętli?

22

Maszyna Turinga, która powróci do wcześniej napotkanego stanu z głowicą do odczytu / zapisu w tej samej komórce dokładnie tej samej taśmy, zostanie przechwycona w pętli. Taka maszyna się nie zatrzymuje.

Czy ktoś może podać przykład ciągłej maszyny, która się nie zapętla?

computability turing-machines halting-problem hollow7
źródło

1

Tylko uwaga: taśma może być inna: warunkiem wystarczającym (ale nie koniecznym) dla nieskończonej pętli, gdy TM wchodzi do tej samej komórki w etapie

i w etapie

w tym samym stanie, jest to, że w etap

fragment taśmy odwiedzanym przez głowicę pomiędzy etapem

, a etap

jest równa odpowiedniej części tuż przed wejściem

.

t_{1}

$t_1$

t_{2} > t_{1}

$t_2 > t_1$

t_{2}

$t_2$

t_{1}

$t_1$

t_{2}

$t_2$

t_{1}

$t_1$

Vor

4

Gdyby baza TM musiała zapętlić się, aby się nie zatrzymać, można dość łatwo rozwiązać problem zatrzymywania baz TM: zapamiętaj wszystkie poprzednie konfiguracje i na każdym kroku sprawdź, czy jesteś w konfiguracji, którą widziałeś wcześniej, a jeśli tak, to wiesz, że rzecz się nie zatrzymuje (w przeciwnym razie, ponieważ zakładamy, że musi ona zapętlać się, aby działać wiecznie, nie będzie działać wiecznie, tj. zatrzyma się, w którym to przypadku ostatecznie wiedzieć o tym).

Patrick87

Zainspirowany odpowiedzią @Niel de Beaudrap: maszyna Turinga może obliczyć sekwencję oeis.org/A014445 i zatrzymać się, gdy otrzyma nieparzystą liczbę. Może obliczyć oeis.org/A016742 jako sumę bieżącą i zatrzymać się, gdy liczba będzie nieparzysta. Mógłby obliczyć, x^2gdzie xcykle pomiędzy -100i 100a cyklowanie odbywa się za pomocą modulo i zatrzymać, gdy wynik jest ujemny. Mógłby obliczyć x%2gdzie x wynosi od zera do dodatniej nieskończoności i zatrzymać, gdy wynik jest równy 2. W języku asemblera wykonaj pętle / while / for, wszystkie przechodzą w dół, mając skok warunkowy, ale sam skok warunkowy niewiele znaczy.

Leonid

Założenie pytania dotyczy tylko maszyn deterministycznych.

Raphael

15

Rozważ TM, która zawsze przesuwa głowicę taśmy w prawo i drukuje specjalny niepusty symbol taśmy na każdym kroku. Oznacza to, że TM nigdy się nie zatrzymuje, ponieważ zawsze przesuwa się w prawo i nigdy nie powtarza stanu, ponieważ po kroku k głowica taśmy znajduje się nad k-tą komórką maszyny. W związku z tym każda konfiguracja maszyny jest inna niż wszystkie inne i maszyna zawsze się zapętla.

Moglibyśmy również niekonstruktywnie pokazać istnienie takich maszyn. Załóżmy, że istnieje sprzeczność, że każda TM, która nigdy się nie zatrzymuje, ostatecznie zapętla się. Oznacza to, że jeśli uruchomisz TM na łańcuchu , w końcu nastąpi jedna z następujących sytuacji: $M$ $w$

zatrzymuje się lub $M$
powtarza konfigurację. $M$

W takim przypadku problem zatrzymania byłby rozstrzygalny w następujący sposób. Biorąc pod uwagę TM i ciąg , symuluj na , w każdym punkcie zapisując zawartość taśmy, aktualny stan i bieżącą pozycję taśmy. Jeśli ta konfiguracja jest duplikatem, wyjście „nie zatrzymuje się”. W przeciwnym razie, jeśli zatrzymuje się na , wyprowadza „zatrzymuje”. Ponieważ jedno z nich z pewnością nastąpi w końcu, proces ten zawsze się kończy, więc dysponowalibyśmy algorytmem problemu zatrzymania, o którym wiemy, że nie istnieje. $M$ $w$ $M$ $w$ $M$ $w$

Mam nadzieję że to pomoże!

templatetypedef
źródło

Hah, pobiłem cię do tej edycji. Zobacz mój komentarz do pytania. Podoba mi się ten sposób wyjaśniania, dlaczego nie wszystkie nie zatrzymujące się TM muszą się zapętlić ... buduje intuicję.

Patrick87

@ Patrick87- Przepraszamy, nie zauważyłem komentarza. Pomyślałem o dodatku w drodze do pracy i usiadłem, żeby do niego wejść, jak tylko wrócę.

templatetypedef

Nie ma problemu, stary ... Cieszę się, że to dodałeś, ponieważ uważam, że to dobry sposób na wyjaśnienie tego. Dodałem go tylko jako komentarz, a nie jako odpowiedź, ponieważ pobiłeś mnie do tego. : D

Patrick87,

W rzeczywistości, jeśli chodzi o problem z zatrzymaniem, takie jak cofanie się i zmiana taśmy ad infinitum wydaje się być „prawdziwym problemem”. Ci spacerowicze, których możesz wykryć.

Raphael

12

Maszyna Turinga, która oblicza wszystkie miejsca po przecinku π (lub dowolną inną nie kończącą się frakcję, w dowolnej bazie) nigdy się nie zatrzymuje i może być napisana na każdej komórce tylko skończoną liczbę razy. Oczywiście fakt, że nie ma przejścia do stanu zatrzymania, byłby martwym rozdaniem, ale jest to przynajmniej naturalny przykład.

f (n) = {\begin{cases} 3 n + 1, & if n is odd; \\ n / 2, & if n is even, \end{cases}

$f(n) = \begin{cases} 3n+1 , & \text{if $n$ is odd}; \\ n/2, & \text{if $n$ is even}, \end{cases}$

f \circ f \circ \dots f (n) = n

$f \circ f \circ \cdots f(n) = n$ , ... które asymptotycznie rozchodzą się w nieskończoność. Jeśli istnieją jakieś sekwencje tego ostatniego rodzaju, oznaczałoby to, że maszyna Turinga, którą opisałem powyżej, nie byłaby powtarzalna, ponieważ taśma byłaby ciągle zmieniana na coraz większe liczby.

Niel de Beaudrap
źródło

Lubię bawić się cyframi pi. TM może zatrzymać się, gdy kwadrat dowolnej cyfry pijest równy dokładnie 7.

Leonid

@Leonid: Z pewnością można rozważyć maszynę Turinga, która przyjmuje pewne dane wejściowe i zatrzymuje się na warunku określonym przez te dane wejściowe. Można nawet określić specyfikację warunków, w których zatrzymuje on część danych wejściowych. I możesz podać dane wejściowe, jak to określisz, ustanawiając ograniczenie, które nigdy nie jest spełnione.

Niel de Beaudrap,

10

Rozważ każdą nie zatrzymującą się maszynę Turinga, która nigdy nie przesunie głowicy odczytu / zapisu w lewo.

JeffE
źródło

Niektóre z nich nadal się zapętlają. </nitpicking>

Raphael

5

Gdyby tak było, problem zatrzymania byłby rozstrzygalny. Wystarczy nagrać każdą parę (taśmę, stan) widzianą podczas wykonywania maszyny Turinga, a maszyna albo się zatrzyma (w takim przypadku oczywiście się zatrzyma), albo zobaczysz parę, którą widziałeś wcześniej, w którym to przypadku maszyna nie zatrzymuje się.

Ponieważ problem zatrzymania jest nierozstrzygalny, nie może to być prawda. (Zobacz inne przykłady dla liczników).

Rekurencyjnie ironiczny
źródło

Co ta odpowiedź dodaje do odpowiedzi templatetypedef ?

Raphael

Chyba nie. Przepraszam, jakoś przegapiłem tę odpowiedź, kiedy napisałem swoją.

Rekurencyjnie ironiczny

Czy maszyna, która nigdy się nie zatrzymuje, zawsze pętli?

Odpowiedzi: