Decidability and the halting problem

Advanced

Introduction

Computers seem able to do anything, given enough time. Turing showed in 1936 that this is false: some precisely stated problems cannot be solved by any program, however clever or however long it runs. The most famous is the halting problem: given a program and its input, will it eventually stop? This limit is not about speed or hardware; it is a mathematical fact, and it explains why no tool can find every infinite loop or every bug.

How it works

A machine decides a problem if it halts on every input with the correct yes or no. A problem is decidable if some decider exists: "is this number prime?" and "does this DFA accept this string?" are decidable.

A problem is recognisable if some machine halts and says yes on every yes-instance, but on no-instances may say no or run forever. The halting problem is recognisable: just run the program, and if it stops, say yes. The trouble is the programs that never stop: waiting gives no answer.

Simulation with a step limit shows the difficulty. Whether the Collatz rule (halve if even, else 3n + 1) reaches 1 from every start is unknown, yet each run is easy to simulate:

def collatz_steps(n, limit=1000):
    steps = 0
    while n != 1:
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        steps += 1
        if steps == limit:
            return None
    return steps


for n in [6, 7, 27]:
    print(f"n={n}: reaches 1 after {collatz_steps(n)} steps")
Open in compiler

The diagonal argument. List some functions from numbers to {0, 1} as the rows of a table. Build a new function g by going down the diagonal and flipping: g(n) = 1 − fₙ(n). Then g differs from every row at the diagonal position, so g is not in the list. Cantor used this idea to show some infinities are bigger than others; Turing used it on programs.

The halting problem is undecidable. Suppose a program halts(p, x) always answered correctly whether program p halts on input x. Build:

def contrary(p):
    if halts(p, p):
        while True: pass     # loop forever
    else:
        return               # halt

Now ask what contrary(contrary) does. If it halts, then halts said it halts, so it loops forever. If it loops forever, then halts said it does not halt, so it halts. Both are impossible, so halts cannot exist. contrary is the diagonal function, built to disagree with every program on its own description.

Reductions. To show a new problem is undecidable, show that a decider for it would give a decider for the halting problem. "Does this program ever print 'hello'?", "Do these two programs compute the same function?" and every non-trivial question about what programs do (Rice's theorem) are undecidable this way.

Syntax

g = [1 - rows[n](n) for n in range(len(rows))]   # the diagonal, flipped
def contrary(p):                                 # disagrees with halts on itself
    if halts(p, p): loop_forever()
    else: return

Example

rows = [
    lambda n: 0,
    lambda n: n % 2,
    lambda n: 1 if n > 2 else 0,
    lambda n: 1,
]
for i, f in enumerate(rows):
    print(f"f{i}:", [f(n) for n in range(4)])
g = [1 - rows[n](n) for n in range(4)]
print("g: ", g)
print("g differs from every row:", all(g[i] != rows[i](i) for i in range(4)))
Open in compiler

Line by line

  1. Each row is a function from numbers to 0 or 1, and the table shows its values for 0 to 3.
  2. g takes the diagonal entry of each row, f0(0), f1(1), f2(2) and f3(3), and flips it.
  3. The check confirms that g differs from row i at position i, for every i.
  4. However many rows the table had, the same construction would give a function not in it. That is exactly how contrary escapes any proposed halts.

Expected result

f0: [0, 0, 0, 0]
f1: [0, 1, 0, 1]
f2: [0, 0, 0, 1]
f3: [1, 1, 1, 1]
g:  [1, 0, 1, 0]
g differs from every row: True

In the real world

Undecidability is why compilers warn about possible problems instead of proving their absence, why antivirus tools cannot detect every malicious program, and why static analysers must sometimes answer "maybe". Practical tools work around it with limits, approximations and timeouts, and by restricting themselves to decidable special cases, such as type checking.

Common mistakes

  • Thinking undecidable means "hard": it means no algorithm exists at all, for any amount of time.
  • Confusing "undecidable" with "unknown": Collatz is unknown; the halting problem is proved impossible.
  • Believing a timeout decides halting: a program that has not stopped yet might still stop later.
  • Reducing in the wrong direction: to prove B undecidable, reduce a known undecidable problem to B.

Best practices

  • Ask whether a question is about what a program does; if so, expect undecidability, and look for a restricted version.
  • When simulating unknown programs, always set a step or time limit and report "unknown", not "no".
  • Write proofs by contradiction carefully: assume the decider, build the contrary program, and show both outcomes fail.

Summary

A problem is decidable if some machine always halts with the right answer, and recognisable if some machine at least says yes to every yes-instance. The halting problem is recognisable but undecidable: a contrary program, built by diagonalisation, contradicts any claimed decider. Reductions carry that impossibility to many other questions about programs.

Quick check

1. What must a decider do?
2. Why is the halting problem recognisable?
3. In the proof, what does contrary(contrary) lead to?
4. To prove problem B undecidable by reduction, you show that…

Key takeaways

  • Deciding means always halting with the right answer; recognising only promises to say yes.
  • No program can decide the halting problem: a "contrary" program would contradict any proposed decider.
  • Reductions spread undecidability to many practical questions about programs.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.