The Halting Problem and Undecidable Problems

Motivation: The First Limit of Computation

Turing in 1936 proved: there exists no program that, for an arbitrary program P and input w, would determine whether P halts on w. This is the Halting Problem. The proof uses an elegant diagonal argument—the same one that Cantor applied for the uncountability of ℝ.

The Halting Problem

HALT: Given a pair ⟨M, w⟩ (the code of a Turing machine M and a word w). Does M halt on w?

Theorem (Turing, 1936): HALT is not decidable.

Proof (Diagonalization):

Suppose there exists a decider H for HALT: H(⟨M,w⟩) = “yes” if M(w) halts; “no” otherwise.

Construct a Turing machine D:

• D(⟨M⟩): if H(⟨M,⟨M⟩⟩) = “yes” → loop forever; if “no” → halt.

What does D(⟨D⟩) do?

• If H(⟨D,⟨D⟩⟩) = “yes” (D halts on ⟨D⟩) → D loops forever → H gave the wrong answer. Contradiction.
• If H(⟨D,⟨D⟩⟩) = “no” (D does not halt) → D halts → Contradiction.

In both cases, H cannot exist. ■

Enumerability Without Decidability

Theorem: HALT ∈ RE (recursively enumerable), but HALT ∉ R (not decidable).

Enumerability: Turing machine U (universal Turing machine) simulates M on w and accepts if M halts. If M(w) = ∞ — U loops forever (does not halt with “no”).

Rice’s Theorem

Theorem (Rice, 1953): Any nontrivial semantic property of computable functions is undecidable.

A property P is nontrivial if:

• Some Turing machine possesses P, some do not.
• P is semantic (depends on the computed function, not the code of the Turing machine).

Corollaries: Undecidable:

• Will M halt on a specific input w₀?
• Does M accept at least one word (L(M) ≠ ∅)?
• Is L(M) regular?
• Are M₁ and M₂ equivalent (L(M₁) = L(M₂))?

Numerical Example

Problem: Prove that the problem {⟨M⟩ : L(M) = ∅} is undecidable by reduction from HALT.

Step 1. Suppose a decider E for E_TM = {⟨M⟩ : L(M) = ∅} exists.

Step 2. Construct a decider H for HALT. Given ⟨M, w⟩. Construct Turing machine M_w:

• M_w(x): run M on w; if M(w) halts — accept (for any x).
• (M_w ignores the input x, only simulates M on w.)

Step 3. L(M_w) = Σ* (all words) if M(w) halts; L(M_w) = ∅ otherwise.

Step 4. E(⟨M_w⟩) = “yes” ⟺ L(M_w) = ∅ ⟺ M(w) does not halt → H(⟨M,w⟩) = ¬E(⟨M_w⟩).

Conclusion: H decides HALT—a contradiction. Hence, E does not exist. ■

Real Application

Cybersecurity: static code analysis for malicious behavior is a direct consequence of Rice’s theorem—one cannot automatically and precisely determine “whether a program is a virus” (semantic property → undecidable). Antivirus programs use heuristics (approximate methods), not exact algorithms.

Additional Aspects

The proof of the undecidability of the halting problem (Turing 1936) is a model of the diagonal argument. From it follow a cascade of undecidabilities: the emptiness problem for Turing machine languages, the equivalence problem for context-free grammars, Hilbert’s tenth problem (decidability of Diophantine equations—Matyasevich’s theorem, 1970). Rice’s theorem generalizes: any nontrivial semantic property of programs is undecidable. This explains why compilers and linters cannot fully guarantee the absence of bugs: for example, code unreachable or the possibility of an infinite loop cannot be generally checked. Modern SMT provers and model checkers bypass this limitation by restricting themselves to finite models or limited depth.

Connection with Other Areas of Mathematics

The connection with Diophantine equations is realized through Hilbert’s tenth problem: in 1900 Hilbert asked about the existence of a general algorithm to decide whether a given polynomial equation has integer solutions. The works of Markov, Robinson, Davis, and Matyasevich’s final result in 1970 showed: the set of solutions to Diophantine equations can encode computations of Turing machines. Thus, the undecidability of the halting problem translates into the undecidability of the existence of integer solutions.

In probability theory, the idea of algorithmic undecidability manifests in Kolmogorov–Solomonoff–Chaitin’s theory of algorithmic randomness. Kolmogorov complexity of a string is the length of the shortest program generating that string; Chaitin proved that the complexity function is uncomputable, essentially reducing its computation to the halting problem. This ties deterministic computability to concepts of “randomness” and entropy.

In algebra and group theory, the known result of Novikov and Boone is the undecidability of the word problem for some finitely presented groups. The construction relies on embedding a Turing machine into a group: a word represents a computation configuration, and asking whether it reduces to the identity is equivalent to the halting question. Similar techniques are used by Adjan and Rabinovich in the context of semigroups and monoids.

In topology and geometry, computational undecidability permeates the problem of recognizing 3-manifolds and constructing homeomorphisms. The works of Matias and others demonstrate the existence of algorithmically undecidable problems for finite descriptions of manifolds and complexes, where the proof relies on encoding Turing machine computations into a combinatorial structure.

Historical Reference and Development of the Idea

Ideas about the limits of mechanical proof were discussed back in the 1920s in the context of Hilbert’s program and the formalization of mathematics. Gödel in 1931 in an article in Monatshefte für Mathematik und Physik formulated the incompleteness theorem, building a formula encoding “this statement is not provable”. His method of arithmetization of syntax became the direct precursor of the formalization of computation.

Turing in 1936, working in Cambridge and then at Princeton under Church’s influence, proposed a model of a machine now bearing his name, and in the article “On Computable Numbers, with an Application to the Entscheidungsproblem” in Proceedings of the London Mathematical Society showed the undecidability of the halting problem and, as a consequence, the negative solution of the decision problem for first-order logic. Almost simultaneously, Church proposed the λ-calculus and formulated an equivalent result, and Post developed his own model of normal forms.

In the postwar period, Markov and his school in the USSR developed the theory of normal algorithms and recursive functions, emphasizing the unified class of computable procedures. In the 1950s–1960s, Rice, Muchnik and others refined the spectrum of undecidable properties of programs, the concept of r.e. sets and the hierarchy by Turing appeared.

By the end of the 20th century, the ideas of the halting problem penetrated practice: the works of Floyd, Hoare, later Clarke, Clarke and Grinier laid the foundations of formal verification, inevitably intersecting with the limits of algorithmic verifiability. In the 21st century, concepts of undecidability, through tools such as model checking and SAT/SMT solvers, have been integrated into industrial means of program and hardware circuit analysis, where the limitations formulated by Turing are regarded as fundamental boundaries of automation.