246 Are the Androids Dreaming Yet? Both analyses lead to a paradox! There is only one way out. There can be no halting procedure. I’m sorry if this is quite convoluted. Philosophical Proof If you find these technical proofs difficult to follow, it may be easier to examine the problem philosophically. Consider the consequence of the existence of a Halting procedure. A Universal Turing Machine is a relatively small program. Roger Penrose gives a three-page example in The Emperors New Mind, and Stephen Wolfram has implemented one using a cellular automaton with as few as five component parts. A Halting Program running on such a machine should be able to compute all the knowledge in the Universe. Every structure, every work of literature, every galaxy could be the output of this single, simple program. My pocket calculator could, theoretically, paint like Picasso and compose like Mozart. All art, knowledge and science would be entirely determined in our Universe and we would have no free will. If you philosophically rebel against this then the Halting Problem must have no solution. Gédel’s Insight Another way to understand this conundrum is through the earlier work of Gédel. Solutions to mathematical puzzles are neat, orderly sequences of statements where the problem is solved step by step. Computers are good at step by step processes. Surely a computer could simply proceed in a painstaking fashion to check all the possible combinations of words and symbols to discover a proof. An analogy might be trying to find your hotel room if you have forgotten the number. You could simply find it by trying every room. As you progressed through each floor, you would try every corridor and retrace your steps to the main hallway before attempting the next. Eventually you would succeed. Finding proofs of theorems is often understood to be the same sort of task: search systematically through all the numbers and you will find the solution. But this is not so: There is a hidden pro