32
$\begingroup$

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?

$\endgroup$
  • 6
    $\begingroup$ Very related question. Community votes, please: duplicate? $\endgroup$ – Raphael Jun 7 '16 at 6:59
  • 9
    $\begingroup$ The task of expressing such a program in as few bits as possible seems to be an issues of Code Golf, less so computer science. $\endgroup$ – Raphael Jun 7 '16 at 7:00
  • 2
    $\begingroup$ I think that Ricky's answer about 5-state TMs is better than the one on the original question. If this one is closed as a dupe, can the answer be moved? $\endgroup$ – David Richerby Jun 7 '16 at 10:37
  • 2
  • 6
    $\begingroup$ You are missing a key detail: you have not specified what language the program must be written in. Your example uses binary lambda calculus -- is that the only language you are interested in? We can see it is trivial to develop a 1 bit program that has unknown halting status, simply by embedding the body of the algorithm directly into the language itself. It's a loophole, but one you have to pay attention to when asking for golf solutions. They love their loopholes! Kolmogov complexity may be an important topic to explore here. $\endgroup$ – Cort Ammon - Reinstate Monica Jun 7 '16 at 15:27
30
$\begingroup$

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
$\endgroup$
  • $\begingroup$ The bottom of the page says: $Date: 2007/11/03, then how it is 26 year old? $\endgroup$ – Falaque Jun 8 '16 at 6:56
  • 1
    $\begingroup$ @Falaque The top of the page states "This page is the author's HTML rewrite of ... February 1990". The text is 26 years old, the rendition into HTML is from (or last updated) in 2007. $\endgroup$ – IMSoP Jun 8 '16 at 9:03
5
$\begingroup$

Collatz conjecture:

The following program always halts:

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

     // Halt here
}

Slight variation (still a conjecture, because it's based on a result from Collatz's one):

For some input the following program will never enter the same state twice (where the state is determined by the value held by "input"):

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

Note that the second program never halts, regardless of whether the first program halts or not.

It is believed that the first program always terminates for any input, however, we don't have the proof of that, and there may still exist some integer for which the program don't halt (there's also a $100 prize for proving it).

The second program is interesting too: it states that the program will never enter the same state twice for some input, which basically requires the first program to have a sequence known to diverge without repeating. It does not only require the Collatz conjecture to be false, but it requires it to be false and without loops, apart from the obvious 1,4,2,1 loop.

  • If Collatz has only looping counter-examples the variation on the conjecture is false

  • If Collatz is false without loops, the variation on the conjecture is true

  • If Collatz is true, the variation is false

  • If Collatz is false both because it has loops and because it has a number for which it diverges, the variation on the conjecture is true (it just requires a number for which it diverges without entering a loop)

I think the variation is more interesting (not just because I found it by accident and noticed it thanks to @LieuweVinkhuijzen), but because it actually requires a real proof. By brute forcing, we may be able to find a loop one day or another (and that will be a loop longer than 70 numbers: current state of the art is that there can't infinite loops shorter than 68 or so), and brute forcing is not interesting: it is just number crunching. However we cannot brute-force an infinite divergent sequence, we don't know if it will really end without a real proof.

EDIT: I skipped the part about Collatz Conjecture sorry, I genuinely answered by heart with an algorithm I read about some years ago, I didn't expect that was already mentioned.

EDIT2: A comment made me notice I wrote the algorithm with a mistake, however, that mistake indeed makes my answer different from Collatz conjecture (but a direct variation of it).

$\endgroup$
  • 1
    $\begingroup$ I think you mean to write input > 1 instead of input >= 1? As it stands now, this program will loop $1\rightarrow 4 \rightarrow 2 \rightarrow 1$ $\endgroup$ – Lieuwe Vinkhuijzen Jun 7 '16 at 11:37
  • $\begingroup$ You are right, I wanted to put a >, however as long as we don't have a proof for halt-ness with > we can't be sure we will reach the 1 -> 4 -> 2 -> 1 loop (in example if it don't terminate for > it don't reach >=) $\endgroup$ – GameDeveloper Jun 7 '16 at 12:36
  • 1
    $\begingroup$ A proof your program with $>=$ does not halt: Suppose the Collatz conjecture is true, then we reach the loop $1421$ on all inputs. Otherwise, if it is false, then we reach the loop $1421$ on some inputs, and on other inputs the sequence either loops elsewhere or else it diverges into infinity (and therefore loops forever). In either scenario, the program with $>=$ never halts, independent of whether Collatz' conjecture is true or not. The program with $>$ halts on all inputs iff the Collatz conjecture is true, which is unresolved. $\endgroup$ – Lieuwe Vinkhuijzen Jun 7 '16 at 12:44
  • 2
    $\begingroup$ There is a much simpler proof that the second program does not halt, which does not invoke the Collatz theorem as a conditional result. The program halts when $n<1$. But neither of the two cases will effect that. If $n=1$, then $n$ becomes $4$. If $n>1$, then $n$ becomes some other number greater than or equal to $1$. In any case, it never goes below $1$, which is necessary to terminate the loop. I do not understand your last comment. $\endgroup$ – Lieuwe Vinkhuijzen Jun 7 '16 at 12:51
  • 1
    $\begingroup$ That's true :) You're right, I should have added 'iff the Collatz conjecture is true' to my first comment. I see your edit, very good. You do not need the second program, because the conjecture 'this program never enters the same state twice' is also unresolved of the first program: it is possible there is a number which does not diverge off into infinity, but instead gets stuck in a large loop somewhere up in very high numbers. $\endgroup$ – Lieuwe Vinkhuijzen Jun 7 '16 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.