## Oranges Discover the Halting Problem!

December 12, 2008 by ed1337

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;
else
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?

### Like this:

Like Loading...

*Related*

on December 14, 2008 at 5:05 pmMensanatorHere’s one way to visualize:

The Big Bang Theory of Binary Numbers

http://mensanator.com/mensanator666/collatz/bang0010.htm