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

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?

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

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).