Here’s a 10-line Python program. Nobody on Earth currently knows whether it ever stops.

f = lambda n: 3*n+1 if n%2 else n//2
stop = seed = 0
while not stop:
    fast = slow = seed = seed + 1
    while True:
        fast = f(f(fast))
        slow = f(slow)
        if fast == slow:
            stop = fast not in (1,2,4)
            break

The halting problem is the question of whether, given a program, we can tell if it will eventually halt or run forever. Theoretically, there must exist programs for which we can’t tell whether they halt. But can we actually build such a program in practice? How short can we make it?

How it works

The program uses the Collatz conjecture, also known as the 3n+1 problem. Starting with some positive integer n, we build a sequence in which the next member is 3n+1 if n is odd, and n/2 if n is even. Every starting value tried so far eventually leads to the “trivial” loop 1 → 4 → 2 → 1 → … The open question is whether there exists a starting value whose sequence leads to a different loop (or escapes to infinity, but our program won’t catch that case).

To detect a loop without remembering every value in the path, the program uses the “tortoise and hare” algorithm: one pointer, fast, advances 2 steps at a time, while the other, slow, advances 1 step at a time. If they ever meet, we’ve found a loop.

If that meeting point is none of 1, 2, or 4, it means we’ve detected a non-trivial loop, and the program halts. If no non-trivial loop exists, the program runs forever.

Unbounded memory

It’s worth noting that unbounded memory, in this case the ability to work with arbitrarily large numbers, is essential for the halting problem. If a program runs on a computer with finite memory, we can always figure out whether it halts by running it on a computer with more memory and recording every state it reaches. Since there is only a finite number of states, we just wait for one to repeat. Repeating states means no halting. It’s the unbounded memory that makes the halting problem undecidable in general.

Python is therefore an ideal language for the job, because its integers don’t have a fixed number of bits and can grow indefinitely. In practice, we will eventually run out of memory, of course. But in principle, if we assume arbitrarily large numbers, no one knows whether this program halts.

So if you ever see it stop, congratulations: you’ve just resolved one of the oldest open problems in mathematics.