Why is Turing's halting problem unsolvable?

A key step in showing that incompleteness is natural and pervasive was taken by Alan M. Turing in 1936, when he demonstrated that there can be no general procedure to decide if a self-contained computer program will eventually halt.

To demonstrate this result, let us assume the opposite of what we want to prove is true. Namely, assume that there is a general procedure H that can decide whether any given computer program will halt. From this assumption we shall derive a contradiction. This is what is called a reductio ad absurdum proof.

So assuming the existence of H, we can construct the following program P that uses H as a subroutine. The program P knows its own size in bits (N)-there is certainly room in P for it to contain the number N-and then using H, which P contains, P takes a look at all programs up to 100 times N bits in size to see which halt and which do not. Then P runs all the ones that halt to determine the output that they produce. This will be precisely the set of all digital objects with complexity up to 100 times N. Finally, our program P outputs the smallest positive integer not in this set, and then P itself halts.

So P halts, P's size is N bits, and P's output is an integer that cannot be produced by a program whose size is less than or equal to 100 times N bits. But P has just produced this integer as its output, and it is much too small to be able to do this, because P's size is only N bits, which is much less than 100 times N. Contradiction! Therefore, a general procedure H for deciding whether or not programs ever halt cannot exist, for if it did then we could actually construct this paradoxical program P using H.

Finally, Turing points out that if there were a theory of everything that always enables you to prove that an individual program halts or to prove that it never does, whichever is the case, then by systematically running through all possible proofs you could eventually decide whether individual programs ever halt. In other words, we could use this theory to construct H, which we have just shown cannot exist. Therefore there is no theory of everything for the halting problem.

Similar reasoning shows that no program that is substantially shorter than N bits long can solve the Turing halting problem for all programs up to N bits long.

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Click one of the buttons below to register using an existing Social Account.

More from Scientific American

• News | 11 hours ago | 2

Bacterium Reverses Autism-Like Behavior in Mice

• News | 12 hours ago

Dyslexia Linked to Brain Communication Breakdown

• TechMediaNetwork | 12 hours ago

Sharks Do Get Cancer: Tumor Found in Great White

• Extinction Countdown | 15 hours ago

Can You Guess Which Country Has the Most Endangered Species?

• News | 16 hours ago

More »

Latest from SA Blog Network

• Bill Nye's Open Letter to Barack Obama

PsiVid | 8 hours ago
• You ever dance with the Devil's Fossils...

History of Geology | 12 hours ago
• The Formula for Kick Starting U.S. Manufacturing Begins with Technology

Observations | 13 hours ago
• Can You Guess Which Country Has the Most Endangered Species?

Extinction Countdown | 15 hours ago
• Advert Informs that Dmitri Mendeleev Knew the Science of Perfect Vodka

PsiVid | 18 hours ago

Science Jobs of the Week

Why is Turing's halting problem unsolvable?

X

Give a 1 year subscription as low as \$14.99

X

X

Welcome, . Do you have an existing ScientificAmerican.com account?

No, I would like to create a new account with my profile information.

X

Are you sure?

X