HOUSE_OVERSIGHT_015934.jpg

244 Are the Androids Dreaming Yet?

[Image of an Impossible Shape/Optical Illusion]

Impossible Shape

That is Turing's argument in a nutshell. But if that was too large a step, let's take the argument a little more slowly and prove it a couple of different ways. First, we will use a proof by counterexample, known by mathematicians as an 'indirect proof'. These may tax your brain. If you want a visual image to help with the idea of an indirect proof, take a look at the impossible shape. It is paradoxical, which means it does not exist. QED.

The Proofs
There are several ways to prove the non-existence of the Halting Program. I am going to present a few in the hope one of them will hit the mark and allow you to see why. The first proof uses a software flowchart. I have laid this out on the assumption the program exists and then attempted to apply it to itself. Unfortunately, the flowchart contains a paradox and thus there can be no Halting Program. The paradox is at once straightforward and confusing. It is a more elaborate version of the liar's paradox: "This sentence is a lie." If the sentence is true it must be false, and if the sentence is false then it must be true.

The Halting Program
Let us suppose there is a Halting Program. Remember that a Halting Program simply takes another program as input and predicts if it will halt or not. It follows there must also be a program called Haltcrash. Haltcrash goes into an infinite loop if it examines a program with input that halts, otherwise it halts itself.

HOUSE_OVERSIGHT_015934