Classical Computability, Completeness, Halting

This article outlines the classical computability framework with particular emphasis on halting and completeness.

Introduction

Within the classical framework, the most important limit on what can be computed by a Turing Machine is completeness, or halting, two manifestations of the same underlying structural feature of algorithmic computation.

Although it is popular to treat Gödel’s incompleteness results as something really difficult to understand — and his original papers on the topic were — the general problem of incompleteness is remarkably easy to grasp. As Greg Chaitin puts it, “Gödel’s theorem…is now considered easy to prove and almost obvious” (Chaitin 1982, p. 942). Below I describe the limits set by completeness and halting the easy way, using tools from algorithmic information theory.

Incompleteness, the Easy Way

The general problem of incompleteness, of which Gödel’s (1931) famous theorem and Turing’s (1936) halting problem are symptoms, is straightforward: within a formal system with a given algorithmic information content, we cannot prove any theorem with an information content exceeding that of the formal system by more than a fixed number of bits. That’s it. Gödel derived his original incompleteness results only by way of a long and ingenious number theoretic proof. At the time, mathematics lacked many of today’s standard tools, such as the general computing framework of Turing and Post, and as a result Gödel’s proof was naturally arduous. But modern developments, especially algorithmic information theory, render its more general form transparent: “if one has ten pounds of axioms and a twenty-pound theorem, then that theorem cannot be derived from those axioms” (Chaitin 1982, p. 942).

Incompleteness and Halting, a Longer Way

The ‘incompleteness’ label relates closely to the paradox of the liar (see Quine 1962): “This statement is false”, a statement which apparently is true if and only if it is false. Gödel’s version for formalisations of number theory is a statement which says of itself that it is unprovable. If such a statement in a given formalisation were provable, then any statement in that system would be provable, because the system would be inconsistent. If, instead, the statement really were unprovable, then that formalisation of number theory would include a true statement which had no proof: if would be incomplete. So, every consistent formalisation of number theory is incomplete.

The general form of this fact is easily understood as a consequence of Turing’s halting problem — which, historically, came second. Given a numbered class of all computer programs which output sets of natural numbers, consider the set of numbers of programs which do not include their own numbers in their output sets. (One way to number programs is just to write them down in numerical order.) Of course this set cannot be listed by any computer program, because that program’s number must be included if it isn’t and mustn’t if it is. (This is reminiscent of Bertrand Russell’s 1908 barber who shaves all and exactly those in his town who do not shave themselves; he must shave himself if he doesn’t and mustn’t if he does.) The solution to the paradox is simply that there can be no effective procedure — i.e., no Turing Machine algorithm, no finite program guaranteed to produce the desired result — for deciding whether an arbitrary program ever outputs a specific number. In other words, we cannot show in advance whether a given arbitrary Turing Machine program outputs a specific number or, equivalently, whether it halts (as opposed to looping or otherwise executing instructions forever). If any particular program does halt, we can find out eventually just by running it for long enough, but in the general case we cannot show that programs fail to halt.

To think of it in another way, using classic Cantor diagonalisation, number as above the programs which output sets of natural numbers, and suppose the halting problem is solvable: suppose there is an effective procedure for deciding whether any given program halts. Then we just embed that procedure in a larger program which determines whether the Nth program outputs an Nth digit and constructs a number D which is different at each location N to the Nth digit output by the Nth program (say, by NOT-ing the Nth digit). But no such program could output D, since it must itself have a number N, and by definition the Nth digit of D is different from the Nth digit output by the program numbered N. The original assumption, that an effective procedure exists which could be used to determine whether the Nth program outputs an Nth digit and thus to construct D, must be flawed. In fact, there cannot be any effective procedure to decide whether an arbitrary program halts (and thus whether it ever outputs an Nth digit).

Incompleteness follows immediately from the unsolvability of the halting problem. Suppose it were the case that every true statement were provable. In particular, suppose every true statement of the form “program N does not halt” can be proven. But the main feature of a formal axiomatic system is that an effective procedure exists for deciding whether a particular proof is valid. (An alternative rendition of a formal axiomatic system is simply as a Turing algorithm for enumerating a set of theorems, generating possible proofs and testing them directly for validity.) So for an arbitrary Turing Machine program N, we just generate all the valid proofs in search of one that proves the halting status of N — and on the assumption that all true statements are provable, we’re guaranteed to find one, eventually. But this contradicts Turing’s theorem that there can be no effective procedure for determining the halting status of an arbitrary program. Therefore, the assumption that every true statement is provable must be rejected.

In fact, the set of numbers of halting programs can be generated by a Turing program (although, of course, we never know when we’re finished), but that set’s complement, the set of numbers of programs which do not halt, cannot. So, not all true statements of the form “program N does not halt” are theorems with associated proofs: not all such true statements are provable. Sets which, like the set of numbers of halting programs, can be generated by a Turing program, are called recursively enumerable, or ‘r.e.’; when, as in the present example, there is no effective test for set membership (equivalently, when the complement of the set is not recursively enumerable) it is called a recursively enumerable nonrecursive set. Put differently, the members of an r.e. set which is nonrecursive can be generated by a Turing algorithm, but not in order. (For an early formulation of such sets in this way, see Post’s elegant 1944 paper; also see Kleene 1952 and Rogers 1967).

Of course, all this is more difficult than the compact general statement at the beginning: within a given formal system, we cannot prove any theorem whose information content exceeds that of the system’s axioms by more than a fixed number of bits. It’s easy now to see the rationale behind that general statement. Consider a program for a given axiom system whose task it is to find the first theorem (say, in order of length of its proof) with an information content exceeding that of the axiom system and the program. Would such a program ever find such a theorem? I.e., would it ever find a theorem which it is impossible to generate with a program and axiom system its size? Of course not! This recalls G.G. Berry’s paradox, first noted by Bertrand Russell (1908): Find the smallest positive integer which to be specified requires more characters than there are in this sentence.

Corollaries for Information Theory

The study of completeness and halting has intimate links with algorithmic information theory. For instance, a corollary of the above limitations on the power of formal systems is that N bits of the right axioms can allow us to establish the halting status of all programs shorter than N but not of any with length N or above. An N-bit number describing the proportion of those programs shorter than N which halt, for instance, together with a generous supply of patience, would allow us to determine exactly which programs do halt: just start testing programs shorter than N bits, and when we’ve found enough that halt to satisfy the N-bit axiom, we’re finished; the procedure itself is guaranteed to halt. The first N bits of Chaitin’s (1975, 1987b; also see Gardner 1979) beautiful random number Omega would also do the trick. (Omega, a maximally complex infinite string, is defined as the probability that Turing Machine U will halt if successive bits of its program are generated by tossing an unbiased coin. In a strong sense, Omega encapsulates all constructive mathematical truth as concisely as possible.) Similarly, it is impossible to prove with N bits of axioms any string’s information content that is greater than a fixed number of bits above N. Proving complexities and establishing halting status for given lengths turn out to be equivalent.

More connections between information theory and completeness are developed in the publications of my colleauge Greg Chaitin and in my own book Mind Out of Matter.

This article was originally published by on and was last reviewed or updated by Dr Greg Mulhauser on .

Mulhauser Consulting, Ltd.: Registered in England, no. 4455464. Mulhauser Consulting does not provide investment advice. No warranty or representation, either expressed or implied, is given with respect to the accuracy, completeness, or suitability for purpose of any view or statement expressed on this site.

Copyright © 1999-2020. All Rights Reserved.