HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

What are very short programs with unknown halting status?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whatshortarewithunknownhaltingstatusprogramsvery

Problem

This 579-bit program in the Binary Lambda Calculus has unknown halting status:

01001001000100010001000101100111101111001110010101000001110011101000000111001110
10010000011100111010000001110011101000000111001110100000000111000011100111110100
00101011000000000010111011100101011111000000111001011111101101011010000000100000
10000001011100000000001110010101010101010111100000011100101010110000000001110000
00000111100000000011110000000001100001010101100000001110000000110000000100000001
00000000010010111110111100000010101111110000001100000011100111110000101101101110
00110000101100010111001011111011110000001110010111111000011110011110011110101000
0010110101000011010


That is, it is not known whether this program terminates or not. In order to determine it, you must solve the Collatz conjecture - or, at least, for all numbers up to 2^256. On this repository there is a complete explanation of how this program was obtained.

Are there (much) shorter BLC programs that also have unknown halting status?

Solution

Yes. ​ This page says there are 98 5-state Turing machines whose halting statuses are unknown. ​ Annoyingly, it does not give any examples of such machines, but this 26-year-old page gives 2 5-state Turing machines whose halting statuses were apparently unknown at that time. ​ (Searching for "simple counter" will take you right between those 2.) ​ I copied them here in case that link goes down:

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

Code Snippets

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

Context

StackExchange Computer Science Q#59344, answer score: 33

Revisions (0)

No revisions yet.