### Incompleteness and Halting. Gödel and Turing.

#### by Danielle Fong

The following occurred to me on a run about two years ago:

It’s not given much press, but the the Halting Problem is intimately related to Gödel’s First Incompleteness Theorem. Indeed it produces it as a correllary. Historically, Gödel’s incompleteness results were proved by hacking arithmetic into a Turing complete system, and this is still how they’re explained today.

There’s a one-to-one bijection between computability of a function and provability of a statement. Hence, the short, and generally accessible proof that the Halting problem is not in general computable for an arbitrary input is also a proof of the ‘most important, surprising result in logic’, namely, that some results, which have may have a perfectly valid truth-value outside a system, cannot be proven within it. One only needs the notion of a computer to follow this line of thinking, which is, in essence, what Gödel did. But the Halting problem is much easier to grasp. I’ve had children understand it, though it does take some walking through!

The interesting thing about the Halting problem is that it’s unsolvable in full generality, independent of whatever special capabilities the system has available. To see this clearly, consider the proof.

Question: Does there exist a (halting) program H which, given any program P, figure out if it would halt, for any input I?

Assume there exists such a program H. Construct a program T as follows.

(Program P, Input I) => (Boolean Halts):

if H(P,I) is true run forever

otherwise halt

Now, call T on itself, with itself as an input. Our assumption presupposes that H always halts. If T would halt on input T, then T will run forever. And if T would run forever on input T, then T would halt. This is a contradiction, so no such program H would exist.

This becomes philosophically and theologically relevant because it doesn’t at all depend upon the form that H might take. Suppose one has funky laws of physics, or happens upon a ‘book of truths’. Or suppose one is some kind of omniscient god, able to just ‘know’ whether something halts or doesn’t. All of these can be wrapped up by saying they’re part of H, whatever H may be, and even if you assume that H^{1} always exists and is well-defined for some set, you cannot also have H be well-defined for programs which include calls to H.

In short, an omniscient entity can’t exist. Not even a god. When speaking amongst nontechnical types this conclusion is usually met with some form of drama: praise or otherwise.

‘Omniscience’, as it happens, doesn’t survive close inspection.

*Notes:*

*[1] Taking the existence of H as given, convention names it a ‘halting oracle’.*

Interesting take. I am a bit of an undecidability freak myself. Wolfram says most important questions are undecidable.

It’s more than just omnicient that does not survive close inspection: conceptualization itself does not survive close inspection. Conceptualization works by distinction, and while it’s a useful abstraction for reasoning, the distinctions don’t hold up under close scrutiny. If you’re interested, Madhyamika is worth studying. It happens to be Buddhist, but you can just look into the logic.

This analogy between computability and completeness occurred to me as well, that’s what lead me to this blog post. I wonder if there is any published work that establish this relation.

Correct me if I’m mistaken, but doesn’t the halting problem simply prove that God can’t be a Turing machine of any sort of implementation, not that God can’t exist?

Doesn’t the paradox you pointed out rule out the existence of a Turing machine that can be self-aware, or one that can discover new truths outside the set it starts with? If this is so, this doesn’t mean self awareness can’t exist, it just means self-awareness can’t be implemented in a Turing machine. Let me illustrate.

I assert that the human mind is not limited by the limitations of computability because it does not merely carry out computation; if the human mind were merely an elaborate Turing machine, Gödel (merely human) would not have been able to comprehend the truth of incompleteness theorem to begin with. Otherwise, you have a self-aware turing machine comprehending its own incompleteness—Doesn’t this violate what you described above?

The history of humans discovering theorems by conjecturing and subsequently seeking and proving a conjecture, or even discovering seemingly long-standing unproven conjectures (which could be new axioms) suggests to me that humans are not merely Turing machines. Somehow the mind is able to grasp at a truth before it is proven and passionately pursue its proof until it is found. Whatever this creative process is, it does not appear to be a merely computational process. And *if* the awareness of the human mind is not limited by the limits of computability, neither would some disembodied omniscient mind. However it arrives at truth, whatever it does, it cannot be said to be computing it. At best, you can conclude that a Turing machine cannot be God (and God cannot be a Turing machine; God does not compute truth).

I don’t think the proof above implies God must be a Turing machine. The only thing it posits is the ability to determine if any particular program halts. This ability contains an internal contradiction (so long as you consider the determination of halting a valid component of a program.) Hence there are certain things that nothing could do, so that the concept of omniscience is flawed.

This doesn’t disprove the existence of God any more than the ‘paradox’ “could an omnipotent God create a rock so heavy that even He could not lift it,” so much as show that the concepts of omniscience and omnipotence are ill defined.

“I assert that the human mind is not limited by the limitations of computability”

Who can say what limits the human (or non-human) mind but the number of thoughts that can be communicated digitally is only countably infinite. Thus there are only countably many Turing machines, yet there are more than countably many functions on the integers (see Cantor) so we are left with uncomputable functions on the integers, i.e. uncomputable real numbers which the mind can perhaps conceive but cannot express.

Of course God could create a rock so heavy He couldn’t lift it. AND He could lift it. I realize this is a contradiction, but God could explain it.

Thanks for the interesting posting.

I am also having trouble with the idea of modelling God using human language, whether formal or informal. As I understand it, the prefix “omni-” implies infinite power, being a metaphysical inference from the fundamental theological tautology: that which exists, exists. (“God” being a synonym for “that which exists”, or “He that is”, in the Biblical tradition.)

There is, of course, an infinite number of things that “nothing can do”. For example, nothing can weeble a wibble, although you can parse the statement “weeble a wibble”, separating it into verb, article and noun. I think what these problems indicate is the insufficiency of the human mind to contemplate self-existence.

The alternative, however, seems to be belief in the truth of the proposition, at least at some point in time, that “Nothing exists”. I do not believe this statement could ever be true, because truth and logic would, by definition, not exist.