**Unformatted text preview:**

Incompleteness via the halting problemJeremy AvigadFebruary 21, 2005On his home page, Haim Gaifman has posted a note that explains how onecan understand the G¨odel sentence in terms of Cantor’s diagonal argument.Here, I explain how it can be understood in terms of the undecidability ofthe halting problem.1 The halting problemLet fm(x) denote the partial function from N to N computed by the Turingmachine coded by the natural number m, under some reasonable encodingof Turing machines. Then the sequence f0, f1, f2, . . . enumerates the unarypartial computable functions, and, moreover, uniformly, in the sense that thefunction g(i, x) ' fi(x) is computable.There is no such enumeration of the unary total computable functions.To see this, suppose k0, k1, k2. . . is an enumeration of computable functionssuch that the function l(i, x) = ki(x) is computable. Then the functiond(x) = l(x, x) + 1 = kx(x) + 1 is also computable. But d cannot be anyfunction ki, since for each i, d(i) = ki(i) + 1.(Alternatively, if we define m(x) = max{k0(x), k1(x), . . . , kx(x)} + 1, weobtain a function m with the stronger property that it “eventually domi-nates” each function ki. To see this, note that for every i, m(x) is greaterthan ki(x) for every x ≥ i.)Let h(m, x) be defined byh(m, x) =½1 if fm(x) is defined0 otherwise1The function h(m, x) is a version of the “halting problem,” since it amountsto a decision, for each m and x, as to whether Turing machine m halts oninput x.The simple diagonalization above gives us an indirect way of seeing thatthe halting problem is unsolvable, i.e. that h is not computable. For, if hwere computable, we could computel(m, x) =½fm(x) if h(m, x) = 10 otherwiseDefining ki(x) = l(i, x) would then yield an enumeration of all the totalcomputable functions, and we have showed that this is impossible.One can prove that h is not computable more directly. Suppose h werecomputable. Then we could define a a partial function s(x) bys(x) '½0 if h(x, x) = 1undefined otherwiseBy our hypothesis, s(x) is a partial computable function. Let m b e suchthat s = fm. Then s(m) is defined, by definition, if and only if h(m, m) = 0;but by the definition of h, this happens if and only if fm(m), i.e. s(m), isundefined.2 Provably total computable functionsIn these notes, we will be interested in effectively axiomatized theories of“interpret a reasonable amount of arithmetic.” In particular, if a consistenttheory T interprets Robinson’s theory Q, then it can represent the notions is a halting computation sequence for Turing machine m start-ing with input xin such a way that for every m, x, and s, s really is a halting computationsequence for machine m on input x if and only if T proves that this is thecase.Such a theory T is said to be Π2-sound if the following holds:For every m, T proves “for every x, machine m halts on input x”if and only if for every x, machine m halts on input x.2A computable function f from the natural numbers to the natural numbers issaid to be provably total in a theory T if there is some machine, m, computingf such that T proves “for every x, machine m halts on input x.” Saying thatT is Π2-sound simply amounts to the assertion that whenever T proves astatement of this form, then machine m really computes a total function.There is a natural way of enumerating all the provably total computablefunctions of such a theory: for each i, if i describes a proof of the statement“for every x, machine m halts on input x” for some i, let kibe the functioncomputed by machine m; otherwise, let kibe the constant zero function.Assuming T is effectively axiomatized, this enumeration is uniform, inthe sense that for every i and x we can compute l (i, x ) = ki(x). But we knowfrom the preceeding section that the sequence k0, k1, k2, . . . cannot enumerateall the computable functions. This means that there must be a computablefunction s that is not on the list. If m is any Turing machine that computess, then m halts on every input, but T does not prove that m halts on everyinput. Thus we have shown that there is a true sentence that cannot beproved in T .In fact, G¨odel’s notion of ω-consistency implies Π2-soundness. For theTuring machine m described in the preceding paragraph, it also implies thatT does not prove (falsely) that m doesn’t halt on some input, since for eachparticular input, T can verify that machine m really does halt. Thus we haveshown:Theorem 2.1 Let T be an ω-consistent, effectively axiomatized theory inter-preting Q. Then there is a sentence ϕ that is neither provable nor refutablein T .This is a weak version of first incompleteness theorem.It is instructive to spell out the argument in greater detail. For each i, letkibe the ith provably total computable function in T . Let s(x) = kx(x) + 1.We have argued that:1. s(x) is a total computable function (since T is effectively axiomatized,and Π2-sound), but2. T doesn’t prove s(x) is total (by the diagonal argument).Why is it that we can prove that s(x) is total, but T can’t? The answer isthat we have made central use of the fact that T is Π2-sound. With slightlystronger assumptions on the amount of arithmetic one can develop in T , thisargument can formalized. Thus, we have shown:3Theorem 2.2 Let T be as above, and assume T interprets a sufficient amountof arithmetic. Then T does not prove its Π2-soundness.This is a weak version of the second incompleteness theorem.3 The incompleteness theoremsWe can obtain better versions of the incompleteness theorems using the moredirect proof of the unsolvability of the halting problem described in Section 1.Given an effectively axiomatized theory T , consider the following attempt tosolve the halting problem: on input m and x, simultaneously do the following:1. simulate Turing machine m on input x, to see if it halts; and2. search for a proof in T that m doesn’t halt on input x.In the first case, output 1 (“yes”), and in the second case, output 0 (“no”).Clearly any “yes” answer is a correct answer to the halting problem.Assuming T is consistent, every “no” answer has to be correct as well. Butwe know that the halting problem is unsolvable, which means that somethinghas to go wrong. The only thing that can possibly go wrong is that theremay be a Turing machine m and an input x, such that m do es not halt oninput x, but T does not prove this fact. The unsolvability of the haltingproblem implies that this is, indeed, the