Co to są bardzo krótkie programy o nieznanym statusie zatrzymania?

32

Ten 579-bitowy program w Binary Lambda Calculus ma nieznany status zatrzymania:

01001001000100010001000101100111101111001110010101000001110011101000000111001110
10010000011100111010000001110011101000000111001110100000000111000011100111110100
00101011000000000010111011100101011111000000111001011111101101011010000000100000
10000001011100000000001110010101010101010111100000011100101010110000000001110000
00000111100000000011110000000001100001010101100000001110000000110000000100000001
00000000010010111110111100000010101111110000001100000011100111110000101101101110
00110000101100010111001011111011110000001110010111111000011110011110011110101000
0010110101000011010

Oznacza to, że nie wiadomo, czy ten program się zakończy, czy nie. Aby to ustalić, musisz rozwiązać hipotezę Collatza - lub przynajmniej dla wszystkich liczb do 2 ^ 256. W tym repozytorium znajduje się pełne wyjaśnienie, w jaki sposób uzyskano ten program.

Czy istnieją (znacznie) krótsze programy BLC, które również mają nieznany status zatrzymania?

MaiaVictor
źródło
6
Bardzo powiązane pytanie . Głosy społeczności, proszę: powielić?
Raphael
9
Zadanie wyrażenia takiego programu w jak najmniejszej liczbie bitów wydaje się być kwestią Code Golfa , a tym bardziej informatyki .
Raphael
2
Myślę, że odpowiedź Ricky'ego na 5-stanowe bazy TM jest lepsza niż ta z pierwotnego pytania. Jeśli ten jest zamknięty jako duplikat, czy można przenieść odpowiedź?
David Richerby,
6
Brakuje kluczowego szczegółu: nie określiłeś języka, w którym program musi być napisany. Twój przykład używa binarnego rachunku lambda - czy to jedyny język, którym jesteś zainteresowany? Widzimy, że to proste, aby opracować 1-bitowy program, który ma nieznany stan zatrzymania, po prostu osadzając treść algorytmu bezpośrednio w samym języku. To luka, na którą należy zwrócić uwagę, pytając o rozwiązania golfowe. Oni kochają swoje luki! Złożoność Kołmogowa może być ważnym tematem do zbadania tutaj.
Cort Ammon - Przywróć Monikę

Odpowiedzi:

30

Tak. Ta strona mówi, że są 98 5-państwowe maszyny Turinga , których zatrzymanie statusy są nieznane. Irytujące, nie podaje żadnych przykładów takich maszyn, ale ta 26-letnia strona podaje 2 5-stanowe maszyny Turinga, których statusy zatrzymania były najwyraźniej w tym czasie nieznane. (Wyszukiwanie „prostego licznika” zabierze Cię bezpośrednio między nimi 2.) Skopiowałem je tutaj na wypadek, gdyby link się zepsuł:

Input Bit   Transition on State     Steps            Comment
             A   B   C   D   E

    0       B1L C1R D0R A1L H1L   > 2*(10^9)       ``chaotic''
    1       B1R E0L A0L D0R C0L

    0       B1L A0R C0R E1L B0L       ?        complex ``counter''
    1       A1R C0L D1L A0R H1L

źródło
Na dole strony jest napisane: $ Data: 2007/11/03, a następnie, jak ma 26 lat?
Falaque,
1
@Falaque U góry strony znajduje się informacja „Ta strona jest autorskim przepisem HTML autora z… lutego 1990 r.”. Tekst ma 26 lat, wersja na HTML pochodzi z (lub ostatnio zaktualizowano) w 2007 r.
IMSoP
5

Hipoteza Collatza:

Następujący program zawsze zatrzymuje się:

void function( ArbitraryInteger input){
     while( input > 1){
            if(input % 2 == 0)
                input /= 2;
            else
                input = (input*3) + 1;
     }

     // Halt here
}

Niewielka odmiana (wciąż domysł, ponieważ opiera się na wyniku z Collatza):

W przypadku niektórych danych wejściowych następujący program nigdy nie wejdzie dwukrotnie w ten sam stan (gdzie stan jest określony przez wartość przechowywaną przez „wejście”):

void function( ArbitraryInteger input){
     while( input >= 1){ // notice the "="
            if(input % 2 == 0)
                input /= 2;
            else
                input = (input*3) + 1;
     }
}

Zauważ, że drugi program nigdy się nie zatrzymuje, niezależnie od tego, czy pierwszy program się zatrzymuje, czy nie.

Uważa się, że pierwszy program zawsze kończy się dla dowolnego wejścia, jednak nie mamy na to dowodu i może istnieć pewna liczba całkowita, dla której program się nie zatrzymuje (jest również nagroda w wysokości 100 USD za udowodnienie) .

Drugi program jest również interesujący: stwierdza, że ​​program nigdy nie wejdzie w ten sam stan dwa razy dla niektórych danych wejściowych, co w zasadzie wymaga, aby pierwszy program miał sekwencję, o której wiadomo, że rozbiega się bez powtarzania. Nie tylko wymaga, aby hipoteza Collatza była fałszywa, ale wymaga, aby była fałszywa i bez pętli , oprócz oczywistej pętli 1,4,2,1.

  • Jeśli Collatz ma tylko zapętlone kontrprzykłady, zmiana przypuszczenia jest fałszywa

  • Jeśli Collatz ma wartość false bez pętli, zmiana przypuszczenia jest prawdziwa

  • Jeśli Collatz ma wartość true, wariant jest fałszywy

  • Jeśli Collatz jest fałszywy zarówno dlatego, że ma pętle, jak i dlatego, że ma liczbę, dla której się rozchodzi, wariacja hipotezy jest prawdziwa (wymaga tylko liczby, dla której rozbiega się bez wchodzenia w pętlę)

Myślę, że ta odmiana jest bardziej interesująca (nie tylko dlatego, że znalazłem ją przez przypadek i zauważyłem dzięki @LieuweVinkhuijzen), ale ponieważ faktycznie wymaga prawdziwego dowodu. Poprzez brutalne wymuszanie, możemy być w stanie znaleźć pętlę jednego dnia lub innego (i będzie to pętla dłuższa niż 70 liczb: obecny stan techniki polega na tym, że nie ma nieskończonych pętli krótszych niż około 68) i brutalny zmuszanie nie jest interesujące: to po prostu chrupanie liczb. Jednak nie możemy brutalnie wymusić nieskończonej rozbieżnej sekwencji, nie wiemy, czy tak naprawdę skończy się bez prawdziwego dowodu.

EDYCJA: Przepraszam, pominąłem część o hipotezie Collatza, szczerze odpowiedziałem na pamięć algorytmem, o którym czytałem kilka lat temu, nie spodziewałem się, że zostało to już wspomniane.

EDYCJA 2: Komentarz zwrócił uwagę, że napisałem algorytm z pomyłką, jednak błąd ten rzeczywiście odróżnia moją odpowiedź od przypuszczeń Collatza (ale jego bezpośrednia odmiana).

Twórca gier
źródło
1
Myślę, że masz zamiar pisać input > 1zamiast input >= 1? W obecnej postaci ten program 1421
zapętli
Masz rację, chciałem umieścić >, ale dopóki nie mamy dowodu na zatrzymanie się, >nie możemy być pewni, że dotrzemy do 1 -> 4 -> 2 -> 1pętli (na przykład, jeśli to się nie skończy >) zasięg >=)
GameDeveloper
1
Dowód, że twój program z się nie zatrzymuje: Załóżmy, że hipoteza Collatza jest prawdziwa, wtedy dochodzimy do pętli na wszystkich wejściach. W przeciwnym razie, jeśli jest to fałsz, to dochodzimy do pętli na niektórych wejściach, a na innych wejściach sekwencja albo zapętla się gdzie indziej, albo rozprasza się w nieskończoność (i dlatego zapętla na zawsze). W obu przypadkach program z nigdy się nie zatrzymuje, niezależnie od tego, czy domysł Collatza jest prawdziwy, czy nie. Program z zatrzymuje na wszystkich wejściach w hipotezie Collatza jest prawdziwy, co jest nierozwiązane. 1421 1421 > = >>=14211421>=>
Lieuwe Vinkhuijzen
2
Istnieje o wiele prostszy dowód, że drugi program się nie zatrzymuje, co nie wywołuje twierdzenia Collatza jako wyniku warunkowego. Program zatrzymuje się, gdy . Ale żaden z tych dwóch przypadków nie wpłynie na to. Jeśli , to staje się . Jeśli , to staje się jakąś inną liczbą większą lub równą . W każdym razie nigdy nie spada poniżej , co jest konieczne do zakończenia pętli. Nie rozumiem twojego ostatniego komentarza. n = 1 nn<1n=1nn > 1 n 1 14n>1n11
Lieuwe Vinkhuijzen
1
To prawda :) Masz rację, powinienem dodać „iff the Collatz hipoteza jest prawdziwa” do mojego pierwszego komentarza. Widzę twoją edycję, bardzo dobrze. Nie potrzebujesz drugiego programu, ponieważ przypuszczenie, że „ten program nigdy nie wchodzi dwukrotnie w ten sam stan”, jest również nierozwiązane z pierwszym programem: możliwe jest, że istnieje liczba, która nie rozchodzi się w nieskończoność, ale zamiast tego utknęła w duża pętla gdzieś w bardzo dużych liczbach.
Lieuwe Vinkhuijzen