Decidability

Maheshwari & Smid · Ch. 7 · Introduction to Theory of Computation

A language is decidable if a Turing machine always halts with the correct answer. It is recognizable if the machine halts on "yes" inputs but may loop forever on "no" inputs. The halting problem is recognizable but not decidable: no algorithm can determine whether an arbitrary program halts.

The halting problem

Can we write a program that takes any program P and input I and decides whether P(I) halts? No. The proof is by diagonalization: assume such a decider H exists, then build a program D that calls H on itself and does the opposite. D halts if and only if D does not halt. Contradiction.

Scheme

; The halting problem: a diagonalization argument.
; We cannot build H, but we can show why.

; Suppose H(program, input) returns #t if program halts on input.
; Define D(x) = if H(x, x) then loop-forever else halt.
; What does D(D) do?
;   If H(D, D) = #t (D halts on D), then D loops. Contradiction.
;   If H(D, D) = #f (D loops on D), then D halts. Contradiction.

; We can demonstrate the structure of the argument:
(define (pretend-H program input)
  ; This is NOT a real halting decider. It's a stand-in.
  ; A real one cannot exist.
  #t)

(define (D x)
  (if (pretend-H x x)
      (let loop () (loop))  ; loop forever
      "halt"))

; D(D) creates a paradox:
; If pretend-H says D halts on D, then D loops.
; If pretend-H says D loops on D, then D halts.
; No consistent H can exist.

(display "The halting problem is undecidable.") (newline)
(display "No program can decide if arbitrary programs halt.") (newline)
(display "This is proved by self-referential contradiction.")

Python

# The diagonalization argument (structure only)
# A real halting decider cannot exist.

def pretend_H(program, inp):
    """Suppose this decides halting. It can't."""
    return True

def D(x):
    if pretend_H(x, x):
        while True: pass  # loop forever
    else:
        return "halt"

# D(D) is paradoxical:
# If H says D(D) halts -> D loops. Contradiction.
# If H says D(D) loops -> D halts. Contradiction.
print("The halting problem is undecidable.")
print("No algorithm can decide if arbitrary programs halt.")

Rice's theorem

The halting problem is just one instance of a general result. Rice's theorem: every nontrivial semantic property of programs is undecidable. "Does this program output 42?" Undecidable. "Does this program ever print anything?" Undecidable. "Is this program equivalent to that one?" Undecidable. The only decidable properties are trivial ones (true for all programs or false for all programs).

Reductions

To prove a new problem is undecidable, reduce a known undecidable problem to it. If the halting problem can be transformed into your problem, then your problem is at least as hard. Reductions are the main proof technique in decidability and complexity theory.

Scheme

; Reduction: proving "does M accept empty string?" is undecidable.
; Reduce from the halting problem.
;
; Given (M, w), build M' that:
;   1. Ignores its own input
;   2. Simulates M on w
;   3. If M halts on w, M' accepts
;
; If we could decide "does M' accept epsilon?",
; we could decide "does M halt on w?"
; But halting is undecidable, so acceptance-on-epsilon is too.

(display "Reduction pattern:") (newline)
(display "  Known undecidable: HALT(M, w)") (newline)
(display "  Target problem:    ACCEPT-EMPTY(M')") (newline)
(display "  Transform: build M' that simulates M on w") (newline)
(display "  If target were decidable, HALT would be too.") (newline)
(display "  Contradiction. QED.")

Python

# Reduction: proving acceptance-on-epsilon is undecidable
# (structure only — the argument, not an actual decider)

print("Reduction pattern:")
print("  Known undecidable: HALT(M, w)")
print("  Target problem:    ACCEPT-EMPTY(M')")
print("  Transform: build M' that simulates M on w")
print("  If target were decidable, HALT would be too.")
print("  Contradiction. QED.")

# Rice's theorem: every nontrivial semantic property is undecidable.
properties = [
    "Does this program output 42?",
    "Does this program ever print anything?",
    "Is this program equivalent to that one?",
    "Does this program halt on all inputs?",
]
print()
print("Rice's theorem: all these are undecidable:")
for p in properties:
    print(f"  - {p}")

Neighbors

🔑 Logic Ch.7 — Gödel's incompleteness theorem and undecidability are deeply related: the halting problem is a logical statement
📝 Proofs Ch.7 — diagonalization: Cantor's diagonal argument proves the same impossibility result as the halting problem proof
🧮 Lean — proof assistants can only check decidable properties; undecidable questions cannot be automated

← Turing Machines by june.kim Complexity →