Terminal Cases
What does it mean to say that a number is computable? Let’s take some examples. All of our examples will have the same form: there exists a program taking a positive integer n as input, which will output a specified finite sequence of digits and then halt.
- There exists a program which will write out the sequence of decimal digits which represents n.
- There exists a program which will write out the value of n × 2.
- There exists a program which will write out 0 if n is odd, and 1 if n is even.
- There exists a program which will write out the value of the n th prime number.
- There exists a program such that, for all n and all m > 0, this program will output the decimal expansion of the fraction n/m in one of two forms: either the complete expansion (if its digits are finite) or, if it contains infinitely recurring digits, the whole number part followed by the recurring fractional part (e.g. 0.3R for 1⁄3).
- There exists a program which will output the n th digit of the decimal expansion of √2.
- There exists a program which will output the n th digit of the decimal expansion of π.
The last two examples are slightly different to those preceding them. There is no program that can output every digit of √2 or of π and then halt, because these numbers are irrational and their decimal expansions have no end. However, the digits of the decimal expansion of π are “countably infinite”, which means that every one of them can be put in correspondance with a whole-number index: for every whole number n there is an n th digit of π, and there is no digit of π that is not the n th digit for some n. We say that π is computable because every one of its digits is computable by a terminating procedure in finite time, even though one could never finish computing all of its digits.
The halting problem indicates the existence of at least one non-computable number. Although there are infinitely many possible computer programs (if our “computer” is a Universal Turing Machine with infinite tape), every possible such program can be placed in correspondance with a whole number, its “Gödel number”: like the digits of an infinite decimal expansion, programs are countably infinite. Some of these programs halt and produce a final output, while others don’t. If we could compute the “halting property” of every program, we could generate a real number the n th digit of whose binary expansion would be either 1 if the n th program halted, or 0 if it did not.
The fact that we cannot find a general procedure that can compute the halting property of every program means that this number is definitely non-computable: we cannot say “there exists a program taking n as input that will output the n th digit” of it. Worse still, thanks to Cantor’s diagonal argument we know that the real numbers are not countable, which means that we cannot place every real number in correspondance with a whole number. Because there are countably infinitely many programs,and uncountably infinitely many real numbers, there must be uncountably infinitely many non-computable real numbers. Worserer and worserer: although there are countably many computably real numbers, the halting problem means that they are not computably enumerable: there is no program which can output, for any given n, the n th computable real number.
M. Beatrice Fazi’s Contingent Computation (review forthcoming) frames computational “contingency” and “indeterminacy” in terms of an ingress of infinity into a finite computational process; but as we have seen here, incomputability is really rather a question of the excess of the uncountably infinite over the countably infinite, an excess which is constructively indicated via diagonalisation. Here’s Fazi’s account:
At the core of Turing’s investigation on computability there is a transversally posed but crucially metaphysical problem: how is it possible to define the infinite in finite terms? The infinity in question is that of the real numbers: a class of values representing quantities along a continuum, like points in a line, whose digits are infinite and thus uncountable. The finite steps, conversely, are those of the deterministic method used by Turing to cope with the dilemma itself. Turing divided the machine’s functionality into small operations, whose complete purpose and conclusion were ruled by their own configuration and whose actions were set out by an equally finite table of behaviour. A Turing machine program is itself a description of an effective method of calculability, facing the possibility of encountering real numbers that cannot be computed with any desired certainty via an enumerable (and hence countable) set of instructions. The impossibility of processing the vast majority of real numbers through a mechanical procedure couples infinity and decidability in a binding logical argument: it is impossible for any Turing machine to prove if any other similar device would be able to write (which means, to calculate) the infinite digits of a real number on its blank tape.
(Contingent Computation, p. 123)
There are several problems here. Firstly, the digits of a real number are not “infinite and thus uncountable”, but countably infinite; the definition of “computability” given above depends upon it, otherwise we could not say that π (for example) was computable. It is the reals themselves that are uncountably infinite, not their digits. Secondly, although the finite “set of instructions” which make up a program are indeed enumerable and countable, what really matters for this argument is the (infinite) countability of programs themselves — the fact that every program can be given a Gödel number. The expression “the vast majority of real numbers” suggests a statistical percentage — 99%? 99.999%? — but there isn’t really a common measure between the countably and the uncountably infinite, such that a ratio like this could make sense. It is simultaneously true that (countably) infinitely many real numbers are computable, and that the probability that any randomly chosen real number is computable is zero.
Finally, it is true that there is no program which can compute the halting property of all other programs, and untrue that there is no program which can compute the halting property of any other program. If you lean very hard on grammatical ambiguity you can read Fazi’s final sentence as saying the first, true, thing; but it certainly isn’t clear that it isn’t also saying the second, untrue, thing, and later statements such as “we just don’t know…whether a program will halt until we run that program” suggest a persistent confusion on this point.
I hope it is clear that I am not merely criticising Fazi for some inapposite word-choices, or accidental clumsiness in presentation. The errors here really are conceptual, and fundamental to the argument she is trying to make — an argument I had high hopes of seeing made well, by a writer who otherwise demonstrated a secure and discerning grasp of the philosophical terrain. In the end, I think Fazi went looking for the wrong thing — for “contingency” in the sense of “indeterminacy” or nowhere-predictability, rather than in the sense of a wholly intrinsically determined limit to totalisability which rules out the possibility of universal computational oversight over the field of computational processes. Fazi is wholly correct to say that “Universal Computation” — the amphiboly that holds that computation is sufficient to model all of reality in simulacrum, or that the underlying physical laws of reality are themselves computational in character — is vexed and undermined at the level of the formal axiomatisation of computation itself. But this does not mean that machines are universally illegible to machines (and hence inscrutable to us — “we just don’t know…”) — only that there can be no machine to which all machines are universally legible.
What is the real connection between the formal, absolute limits indicated by the halting problem and Rice’s Theorem, and the practical difficulty of writing bug-free software that does just what one wants it to? One possible answer is “nothing”: the latter would obtain even if we had to hand a “halting Oracle” that could tell us instantly whether any program presented to it would terminate, although perhaps we could use this Oracle to begin building a larger edifice of verification, finding ways to reason via “if X terminates, then Y” statements towards otherwise-incalculable verities. Let’s call this the “minimalist” answer. For the minimalist, the power of halting Oracles would have to be demonstrated step-by-step, gradually and constructively introducing new knowledge into the world. Conversely, the “maximalist” answer would be that a halting Oracle would instantly and unrepudiatably establish a new regime of truth, such that all of our ad hoc, trial-and-error software development practices would instantly be swept away. We would write programs with the assistance of theorem provers that would connect the dots between specification and implementation with causality-defying swiftness and certitude, as if an angel from the future could be summoned at will to tell us whether our intimations about the behaviour of our software were correct.
I am inclined towards the minimalist view, but do not know how it might be nuanced or justified, or what other formal issues are entangled in this question. My chief reason for being so inclined is that I am skeptical that the combinatorial wilderness in which our programs live could be very significantly reduced and tamed even by oracular input. But that may be precisely because I have no way of seeing, in the absence of such input, the hidden structure of that wilderness, its underground streams and ley-lines, by which an oracle-equipped traveller could navigate. And, as Lucca’s evolutionary explorations show, supernatural guidance may not be the only way we have to surface implicit order within what first appear as intractable ontological thickets.