Computability and the Halting Problem: What a Machine Will Never Solve

What Does It Mean to “Compute”?

In 1936, Alan Turing, in parallel with Gödel and independently, proved another fundamental limit: there exist problems that are inherently uncomputable—no machine (and likely no algorithm) will ever be able to solve them.

The “Halting Problem”: is it possible to write a program that, for any other program and input data, determines whether that program will halt (produce a result) or loop forever?

Turing proved: no, it is not possible. Suppose such a program H(p, x) exists. Then one can construct a program D which: takes program p, runs H(p, p), and if H says “will halt”—loops forever, if “will loop forever”—halts. What does H(D, D) do? A contradiction is inevitable.

The Class of Uncomputable Problems

The halting problem is only the first among a vast class of uncomputable problems. “Hilbert’s tenth problem”: determine whether a given Diophantine equation has an integer solution. Yuri Matiyasevich (1970) proved: uncomputable. “Post’s correspondence problem”: uncomputable. Many “practical” program verification problems are uncomputable.

The complexity class P and NP: a million dollars is offered for this. Problems in class P can be solved in polynomial time. Problems in class NP—the solution can be checked in polynomial time, but it is unknown whether it can be found in polynomial time. If P=NP—most cryptography will need to be redone.

This is not just theory: scheduling problems, logistics optimization, software verification—all these are NP-complete problems, requiring heuristics and approximate solutions, because an exact solution is computationally unattainable.

Question for reflection: There are problems that are fundamentally unsolvable by any algorithm. What “unsolvable” problems exist in your profession—situations where there is no algorithm, only judgment?