Что такое очень короткие программы с неизвестным статусом остановки?

Эта 579-битная программа в двоичном лямбда-исчислении имеет неизвестный статус остановки:

01001001000100010001000101100111101111001110010101000001110011101000000111001110
10010000011100111010000001110011101000000111001110100000000111000011100111110100
00101011000000000010111011100101011111000000111001011111101101011010000000100000
10000001011100000000001110010101010101010111100000011100101010110000000001110000
00000111100000000011110000000001100001010101100000001110000000110000000100000001
00000000010010111110111100000010101111110000001100000011100111110000101101101110
00110000101100010111001011111011110000001110010111111000011110011110011110101000
0010110101000011010

То есть неизвестно, завершается ли эта программа или нет. Чтобы определить это, вы должны решить гипотезу Коллатца - или, по крайней мере, для всех чисел до 2 ^ 256. В этом хранилище есть полное объяснение того, как эта программа была получена.

Существуют ли (значительно) более короткие программы BLC, которые также имеют неизвестный статус остановки?

Да. Эта страница говорит , что есть 98 5-состояние машины Тьюринга , чьи запинающийся статусы неизвестны. Досадно, что здесь не приводятся примеры таких машин, но на этой 26-летней странице представлены 2 машины Тьюринга с 5 состояниями, чьи состояния остановки были, по-видимому, в то время неизвестны. (Поиск «простой счетчик» приведет вас прямо к тем 2). Я скопировал их здесь на случай, если эта ссылка выйдет из строя:

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

Гипотеза Коллатца:

Следующая программа всегда останавливается:

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

     // Halt here
}

Небольшое отклонение (все еще предположение, потому что оно основано на результате Коллатца):

Для некоторых входных данных следующая программа никогда не войдет в одно и то же состояние дважды (где состояние определяется значением, сохраненным в «входе»):

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

Обратите внимание, что вторая программа никогда не останавливается, независимо от того, останавливается ли первая программа или нет.

Считается, что первая программа всегда завершается для любого ввода, однако у нас нет доказательств этого, и все еще может существовать некоторое целое число, для которого программа не останавливается (есть также приз в 100 долларов за доказательство этого) ,

Вторая программа также интересна: она утверждает, что программа никогда не будет входить в одно и то же состояние дважды для некоторого ввода, что в основном требует, чтобы первая программа имела последовательность, которая, как известно, расходилась без повторения. Это не только требует, чтобы гипотеза Коллатца была ложной, но она требует, чтобы она была ложной и без петель , кроме очевидной петли 1,4,2,1.

• Если у Коллатца есть только циклические контрпримеры, то изменение гипотезы ложно

• Если Collatz ложно без петель, изменение гипотезы верно

• Если Collatz истинно, изменение ложно

• Если Collatz имеет значение false и потому, что у него есть петли, и потому, что у него есть число, для которого он расходится, изменение гипотезы верно (ему просто требуется число, на которое он расходится, не входя в цикл)

Я думаю, что вариант более интересен (не только потому, что я нашел его случайно и заметил благодаря @LieuweVinkhuijzen), но и потому, что он действительно требует реальных доказательств. Путем грубой форсировки мы можем найти петлю в тот или иной день (и это будет петля длиннее 70 чисел: в настоящее время известно, что не может быть бесконечных петель короче 68 или около того), и грубой форсировать не интересно: это просто хруст. Однако мы не можем грубо заставить бесконечную расходящуюся последовательность, мы не знаем, действительно ли она закончится без реального доказательства.

РЕДАКТИРОВАТЬ: я пропустил часть о гипотезе Коллатца извините, я искренне ответил наизусть с алгоритмом, который я прочитал несколько лет назад, я не ожидал, что это уже упоминалось.

РЕДАКТИРОВАТЬ 2: Комментарий заставил меня заметить, что я написал алгоритм с ошибкой, однако, эта ошибка действительно отличает мой ответ от гипотезы Коллатца (но это его прямое изменение).