Apa program yang sangat singkat dengan status penghentian yang tidak diketahui?

Program 579-bit dalam Binary Lambda Calculus ini memiliki status penghentian yang tidak diketahui:

01001001000100010001000101100111101111001110010101000001110011101000000111001110
10010000011100111010000001110011101000000111001110100000000111000011100111110100
00101011000000000010111011100101011111000000111001011111101101011010000000100000
10000001011100000000001110010101010101010111100000011100101010110000000001110000
00000111100000000011110000000001100001010101100000001110000000110000000100000001
00000000010010111110111100000010101111110000001100000011100111110000101101101110
00110000101100010111001011111011110000001110010111111000011110011110011110101000
0010110101000011010

Artinya, tidak diketahui apakah program ini berakhir atau tidak. Untuk menentukannya, Anda harus menyelesaikan dugaan Collatz - atau, setidaknya, untuk semua angka hingga 2 ^ 256. Pada repositori ini ada penjelasan lengkap tentang bagaimana program ini diperoleh.

Apakah ada (banyak) program BLC pendek yang juga memiliki status penghentian yang tidak diketahui?

Iya nih. Halaman ini mengatakan ada 98 5-negara mesin Turing yang status tersendat-sendat tidak diketahui. Anehnya, ia tidak memberikan contoh mesin seperti itu, tetapi halaman berusia 26 tahun ini memberikan 2 mesin 5-state Turing yang status penghentiannya tampaknya tidak diketahui pada waktu itu. (Mencari "penghitung sederhana" akan membawa Anda tepat di antara 2. itu.) Saya menyalinnya di sini jika tautannya turun:

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

Dugaan collatz:

Program berikut selalu berhenti:

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

     // Halt here
}

Variasi sedikit (masih berupa dugaan, karena didasarkan pada hasil dari Collatz):

Untuk beberapa input, program berikut tidak akan pernah memasuki status yang sama dua kali (di mana status ditentukan oleh nilai yang dimiliki oleh "input"):

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

Perhatikan bahwa program kedua tidak pernah berhenti, terlepas dari apakah program pertama berhenti atau tidak.

Diyakini bahwa program pertama selalu berakhir untuk input apa pun, namun, kami tidak memiliki buktinya, dan mungkin masih ada beberapa bilangan bulat yang tidak dihentikan oleh program (ada juga hadiah $ 100 untuk membuktikannya) .

Program kedua juga menarik: ia menyatakan bahwa program tidak akan pernah memasuki keadaan yang sama dua kali untuk beberapa input, yang pada dasarnya mengharuskan program pertama untuk memiliki urutan dikenal menyimpang tanpa mengulangi. Ini tidak hanya mensyaratkan dugaan Collatz salah, tetapi juga mensyaratkan dugaan itu salah dan tanpa loop , terlepas dari loop 1,4,2,1 yang jelas.

• Jika Collatz hanya memiliki perulangan contoh, variasi pada dugaan itu salah

• Jika Collatz salah tanpa loop, variasi pada dugaan itu benar

• Jika Collatz benar, variasinya salah

• Jika Collatz salah baik karena memiliki loop dan karena memiliki nomor yang menyimpang, variasi pada dugaan itu benar (itu hanya membutuhkan nomor yang menyimpang tanpa memasuki lingkaran)

Saya pikir variasinya lebih menarik (bukan hanya karena saya menemukannya secara tidak sengaja dan menyadarinya berkat @LieuweVinkhuijzen), tetapi karena itu sebenarnya membutuhkan bukti nyata. Dengan memaksa kasar, kita mungkin dapat menemukan loop satu hari atau yang lain (dan itu akan menjadi loop lebih dari 70 angka: keadaan saat ini adalah bahwa tidak ada loop tak terbatas lebih pendek dari 68 atau lebih), dan kasar memaksa tidak menarik: itu hanya angka-angka. Namun kita tidak dapat dengan kasar memaksa urutan divergen tak terbatas, kita tidak tahu apakah itu akan benar-benar berakhir tanpa bukti nyata.

EDIT: Saya melewatkan bagian tentang dugaan Collatz, saya benar-benar menjawab dengan algoritma yang saya baca beberapa tahun yang lalu, saya tidak berharap itu sudah disebutkan.

EDIT2: Sebuah komentar membuat saya memperhatikan saya menulis algoritma dengan kesalahan, namun, kesalahan itu memang membuat jawaban saya berbeda dari dugaan Collatz (tetapi variasi langsung dari itu).