Posts Tagged ‘Halting Problem’


Eureka! It’s the halting problem, or to be more precise Collatz’s Conjecture. The algorithm is as follows:

while (n > 1)
  if (n is even)
    n := n / 2;
    n := 3n + 1;

where n is an integer greater than 0.

If we try a test cases the pattern is as follows:

n = 2: 2, 1, halt.

n = 3: 3, 10, 5, 16, 8, 4, 2, 1, halt.

n = 7: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, halt.

Hopefully, none of you have ever written any code like this. The question is, will this algorithm always terminate (halt), or are their certain values of n for which it will loop forever?

Collatz is a classic example of the Halting Problem, which Alan Turing proved that there is no way we can write a generic program that can tell if all possible programs will halt or not. Obviously the halting problem is solvable for some/most programs – the first Hello World! you ever wrote hopefully did halt. Microsoft’s Terminator research project can be used to tell whether a large numer of typical programs will halt or not, but the Collatz’s algorithm still eludes them!

If you want to have a play around with this, I have written a Java program to save you the effort (albeit minimal) of doing it yourself. Let me know how you get on – I suggest trying the number 27.

A final thought: what is the best way to visualise all the data: say n = 1 to 1,000,000?

Read Full Post »