patternMajor
What are very short programs with unknown halting status?
Viewed 0 times
whatshortarewithunknownhaltingstatusprogramsvery
Problem
This 579-bit program in the Binary Lambda Calculus has unknown halting status:
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?
01001001000100010001000101100111101111001110010101000001110011101000000111001110
10010000011100111010000001110011101000000111001110100000000111000011100111110100
00101011000000000010111011100101011111000000111001011111101101011010000000100000
10000001011100000000001110010101010101010111100000011100101010110000000001110000
00000111100000000011110000000001100001010101100000001110000000110000000100000001
00000000010010111110111100000010101111110000001100000011100111110000101101101110
00110000101100010111001011111011110000001110010111111000011110011110011110101000
0010110101000011010That 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 H1LCode 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 H1LContext
StackExchange Computer Science Q#59344, answer score: 33
Revisions (0)
No revisions yet.