The Emergence of Computability

The incompleteness theorems depend on the effectiveness of axioms and proof procedures. To investigate that condition, one must clarify what it means for a method to be mechanical.

The Entscheidungsproblem asked for a procedure deciding whether an arbitrary first-order formula is logically valid. Hilbert and Ackermann gave the question a prominent formulation in their 1928 textbook. A negative answer required more than the failure of known methods: it required a mathematical account broad enough to represent every proposed effective procedure.

During the 1930s, several approaches converged. Church studied lambda-definability; Herbrand and Gödel developed general recursion, which Kleene investigated systematically; Turing analyzed the steps available to a human calculator following fixed rules; and Post proposed a closely related operational account.

Computation by recursion

Primitive recursion defines a function by an initial value and a rule for passing from one case to the next:

Addition and multiplication can be defined in this manner. The recursion follows a supplied natural-number argument, so the definition carries an explicit finite progression toward the initial case.

Primitive recursive functions form a substantial class, but not every total computable function belongs to it. Work by Ackermann and Rózsa Péter helped clarify the reach of different recursion schemes. Péter's systematic investigation of recursive functions made the structure of recursion itself a subject of mathematical study.

General computation allows searches with no predetermined bound. Given a suitable predicate $P(x,y)$, search for the least $y$ such that $P(x,y)$ holds. If no such $y$ exists, the computation does not return a result.

Partial functions are therefore essential. An effective procedure need not terminate on every input. Its domain is the set of inputs on which it does terminate.

Turing's analysis of a calculator

Turing's 1936 paper analyzes computation through finitely specified states, a tape divided into cells, and elementary operations of reading, writing, and moving.

The tape is unbounded, but at any finite stage only finitely many steps have occurred. The machine's transition table is finite. Its next transition is determined by its current state and the symbol being read.

This model was motivated by an analysis of what a person following a fixed routine could do, rather than by a design for a particular electronic computer. A complicated operation must be decomposed into locally specified steps.

A universal machine can interpret an encoded machine description and simulate that machine on a supplied input. The description itself becomes data. This is the computational counterpart of the earlier encoding of formulas and proofs by numbers.

Universality does not mean that all computations finish or run efficiently. It says that one effective interpreter can reproduce the behavior of any machine in the specified model.

A small machine makes the distinction between a finite description and an unbounded computation concrete. Begin with unary increment, then compare a halting run, an exact cycle, and an unfinished run.

Equivalent models and the Church–Turing thesis

Church used lambda-definability to formulate an account of effective calculability and establish an undecidability result. The lambda calculus represents function abstraction and application; computation proceeds by substitution and reduction. Its internal workings are developed in the Curry–Howard note.

Equivalence results connect lambda-definable functions, general recursive functions, and Turing-computable functions. These are mathematical theorems relating precise formal definitions.

The Church–Turing thesis makes a further identification: the effectively calculable numerical functions are those captured by these models. Since “effectively calculable” begins as an informal notion, the thesis is not another equivalence theorem between two previously formalized classes.

Its support includes the analysis of mechanical procedures, the convergence of differently motivated models, and the ability to translate new effective programming formalisms into the established ones.

The historical paths were not wholly isolated. Researchers corresponded, read related work, and revised their assessments. Post's independent 1936 formulation is important without requiring the inaccurate conclusion that every contributor developed every relevant idea without knowledge of the others.

Why the halting problem is undecidable

Suppose an algorithm $H(p,x)$ always terminates and correctly decides whether program $p$ terminates on input $x$.

Construct a program $D$ with the following behavior on input $p$:

1. Compute $H(p,p)$.
2. If the answer says that $p$ terminates on itself, continue forever.
3. Otherwise, terminate.

Let $d$ be the code of $D$. If $H(d,d)$ predicts termination, $D(d)$ continues forever. If it predicts nontermination, $D(d)$ terminates. Either outcome contradicts the assumed correctness of $H$.

This is a modern diagonal presentation of the undecidability argument. Turing's original paper used its own terminology and problems about computable sequences; the modern halting formulation should not be passed off as a verbatim reproduction.

The argument rules out a total decision procedure for all program/input pairs. It does not prevent us from proving termination or nontermination for many particular programs.

Semidecision and reduction

Termination can be recognized when it happens: simulate a program, and accept if it stops. If it never stops, the simulation does not return a negative answer.

A set is computably enumerable, or semidecidable, when there is a procedure that eventually accepts each member, with no requirement to terminate on nonmembers. Decidability requires correct termination in both cases.

First-order validity is semidecidable because complete proof systems permit proof enumeration. Church's negative solution shows that validity is not decidable in general. Completeness therefore gives a systematic search with a one-sided guarantee, not a universal yes-or-no algorithm.

A reduction transfers an impossibility result to another problem. For example, given a program $p$ and input $x$, construct a new program that, on any input, first simulates $p(x)$ and returns $0$ if that simulation terminates. The new program computes the total zero function exactly when $p(x)$ halts.

A decision procedure recognizing this property from arbitrary program descriptions would decide halting. Hence no such procedure exists.

Rice's theorem generalizes this pattern: every nontrivial property of the partial function computed by a program has an undecidable index set. The qualification “of the computed function” matters. A syntactic property such as the length of the program text is a different kind of question and can be decidable.

Kleene's normal form and fixed points

Kleene organized computability through normal forms and general theorems about effective operations. One formulation of his normal form theorem is

Here $T$ is a primitive recursive predicate checking whether $y$ encodes a suitable terminating computation, $U$ extracts its output, and $\mu$ performs unbounded minimization. The symbol $\simeq$ allows both sides to be undefined.

Checking one proposed computation is finite and effective. Finding a terminating computation has no uniform bound, and one may not exist. Replacing unbounded minimization with bounded search would remove precisely the partiality the theorem must capture.

Kleene's recursion theorem is another structural result. In a standard numbering, every total computable transformation $f$ of program indices has an index $e$ satisfying

The equality concerns computed partial functions, not necessarily equality of program texts. The theorem supplies effective fixed points and supports computational self-reference. It does not require that every program literally inspect a file containing its own source code.

These results turned a collection of computing formalisms into a theory with reusable methods.

Relative computability and Post's problem

Turing later considered machines equipped with an oracle for a specified set. An oracle answers membership questions that need not be decidable by an ordinary machine. The resulting notion measures which problems become computable when another problem is treated as an available resource.

Write $A\leq_T B$ when membership in $A$ can be decided using an oracle for $B$. Sets equivalent under this relation occupy the same Turing degree.

Post asked whether there are computably enumerable degrees strictly between the computable sets and the halting problem. Friedberg and Muchnik independently answered this through the priority method in the 1950s.

The broad construction organizes potentially conflicting requirements by priority. When satisfying one requirement disrupts another, the argument controls how often such disruption can occur. The method made it possible to construct sets with finely specified computational relationships.

Undecidability was thus only the beginning. Computability theory investigates different degrees of unsolvability and the resources needed to pass between them.

Hilbert's tenth problem

Hilbert's tenth problem asked for an algorithm deciding whether a polynomial equation with integer coefficients has an integer solution.

Davis, Putnam, Julia Robinson, and Matiyasevich developed the negative answer through a long sequence of results. Their work culminated in 1970 in the characterization of computably enumerable sets as Diophantine sets: membership can be represented by the existence of solutions to an appropriate polynomial equation.

The mechanism can be glimpsed in an elementary example. A natural number $n$ is composite exactly when

The general theorem represents vastly more complicated computably enumerable conditions in this existential polynomial form. In particular, a halting condition can be translated into the solvability of a polynomial equation.

The earlier Davis–Putnam–Robinson work reduced the remaining difficulty to the Diophantine representation of suitable exponential growth. Matiyasevich supplied the missing ingredient using number-theoretic properties associated with Fibonacci numbers. This was a cumulative achievement, not a problem solved by one isolated application of Gödel's theorem.

The result carries undecidability into a classical mathematical subject. A finite polynomial equation can encode a question for which no universal solution procedure exists.

Beyond the existence of algorithms

An undecidability theorem rules out an algorithm that always answers a specified general question. It does not make every restricted instance intractable. Decidable fragments, heuristics, and proof-guided methods remain useful.

Moreover, the existence of an algorithm does not tell us whether it is efficient. Complexity theory asks about time, space, and proof size, and will enter the series through SAT and SMT.

Another question concerns the internal structure of proofs. Gentzen showed that derivations could be transformed and analyzed in ways that reveal their mathematical strength. The next note follows that development.

Sources and further reading

• Alonzo Church, “An Unsolvable Problem of Elementary Number Theory” and “A Note on the Entscheidungsproblem” (1936).
• Alan Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem” (1936–1937), and “Systems of Logic Based on Ordinals” (1939).
• Stephen C. Kleene, Introduction to Metamathematics (1952); Rózsa Péter, Rekursive Funktionen (1951).
• Emil Post, “Finite Combinatory Processes—Formulation 1” (1936) and “Recursively Enumerable Sets of Positive Integers and Their Decision Problems” (1944).
• Yuri Matiyasevich, Hilbert's Tenth Problem and accompanying materials, for the successive contributions to the negative solution.