Department of Computer Science

University of Waterloo

In 1936, Alan Turing, in one of the great intellectual feats of the 20th century, proved that there exist natural computational problems for which there exists no algorithm that will unerringly solve them. For example, the problem

Given Turing machine *T* and input *w*,
does *T* halt on input *w*?

is unsolvable. Today, dozens of problems are known which are unsolvable.
(See, for example, G. Rozenberg and A. Salomaa, *Cornerstones of
Undecidability*, Prentice Hall, 1994.)

There are several possible objections to the applicability of this result to real-world programs. At first glance, Turing's result does not rule out the possibility that one might be able to solve the halting problem for all programs that one encounters in real life; it is at least conceivable that only enormously large programs create problems.

However, this objection can be disposed of by observing that a universal Turing machine can simulate any other Turing machine, so if one could solve the halting problem for a universal TM, then one could solve the halting problem for any TM. And some very "small" universal Turing machines are known: for example, there are universal TM's with 24 states on 2 symbols, and 2 states on 18 symbols [1]. So the halting problem is unsolvable even for a specific, reasonably small program. And the existence of small universal TM's strongly suggests that there are short real-world programs for which it will not be easy to decide whether or not they halt.

Another objection to the relevance of Turing's result is that it does not apply to real-world programs since it is based on Turing machines, a purely theoretical model that has access to an unbounded storage tape. Since real machines do not have access to arbitrarily large amounts of storage, perhaps Turing's result says nothing about real-world programs.

This criticism is technically correct, since every real-world machine is
a finite-state machine. However, one possible answer to this objection
is that if a program has access to even a very small amount of storage,
say 5000 bytes, then the number of possible states is so large as to
preclude solving the halting problem before the Sun burns out.
In fact, there exist very short programs for which
we cannot currently determine,
*in practice*,
whether or not they halt -- even if they are
restricted to using some very small amount of storage, on the order of
several thousand bytes. (Of course, *in theory* the halting problem
is solvable for any machine with access to only a finite amount of storage.)

More precisely, **there exist very short
inputless Python programs** (where operations can be done
on integers of arbitrary size) **for which no one can currently decide whether
or not they halt**.

n = 1 s = 0 while s != n: n = n + 2 s = 0 for d in range(1, n): if n%d == 0: s = s + d

This program attempts to find an odd perfect number. (A perfect
number is a number *n* which is equal to the sum of its
positive divisors, excluding *n* itself. For example,
6 is a perfect number because 6 = 1 + 2 + 3.) No odd
perfect number is currently known, and it is known that the
least such number is at least 10^300 (see
R. P. Brent, G. L. Cohen, and H. J. J. te Riele, Improved
techniques for lower bounds for odd perfect numbers,
*Math. Comp.* **57** (1991), 857-868;
MR 92c:11004.)
Hence it
is currently unknown whether or not this program will ever terminate,
and even if it can be proved to terminate, the running time
on the fastest known computer will exceed the current age
of the universe by a huge factor.

def is_prime(n): for i in range(2, n): if n%i == 0: return False return True n = 4 flag = False while not flag: n = n + 2 i = 3 flag = True while flag and 2*i <= n: if is_prime(i) and is_prime(n-i): flag = False i = i + 2

In fact, Conway proved that a simple generalization of the
"3*n*+1" problem is unsolvable (see J. H. Conway, Unpredictable
iterations, in *Proc. of the 1972 Number Theory Conference*,
University of Colorado, pp. 49-52).

Dean Hickerson suggests the following variant:

n = 7 while n != 1: if n%2==0: n = n//2 else: n = 5*n + 1

Does this Python program halt? The answer is believed to be "no", but no one currently knows how to prove it.

An even shorter version of this program was found by Christoph Ulshoefer in December 2017. Here it is:

n=7 while n-1:n=(n//2,5*n+1)[n%2]And Artem Kholodov improved this to 32 characters in 2019:

n=7 while~-n:n=(n//2,5*n+1)[n%2](With only 32 characters, this is the shortest Python program I know for which no one currently knows whether it halts. Can you find a shorter one?)

These examples should convince you that solving the halting problem, even for very simple programs in real life, is not always very easy.

*Thanks to Arlo Shallit for converting my old Pascal programs to
python!
*

- Y. Rogozhin, Small universal Turing machines,
*Theoretical Computer Science***168**(1996), 215-240.

Back to CS 360 home page cs360@descartes