This is computing machine A. A solves problems in arithmetic. It receives a problem written on paper, And it prints the answer. It always prints the right answer. Here’s another computing machine, C. C plays checkers. It receives the current state of the board . . . And it prints how it would move one of the red pieces. C plays checkers so well - it will never lose a game. A and C are machines we can already build today, and computers keep getting smarter and smarter. So will they eventually be able to do everything? Let’s feed A with a board of checkers. A was not designed to handle this kind of input, and when it tries to process it, it gets stuck. The same thing happens to C when fed with a question in arithmetic. Let’s draw a blue print of A. This blue print is detailed down to the level of the logic circuits, and it fully defines how A works. We are now finally ready to introduce a marvelous machine called H. H solves what is known as the halting problem: It can analyze the blue print of another machine, and determine which inputs are good for it, and which will cause it to get stuck. It receives the blue print of the machine to be tested, and an input to test it with. Based on the blue print, H simulates the given machine on the given input . . . and then determines if it gets stuck or not. H solves the halting problem perfectly. It always prints the right answer. Here are two more examples with the blue print of the checkers machine. H is a nice machine, but can we really build it? We’ll now prove that its very existence . . . is logically impossible. Let’s assume that H does exist. We’ll place it on this stand for reasons that will be made clear in a minute. Recall that we assume H solves the halting problem perfectly: it should always print the correct answer. We are about to put this to the test. This is a photocopying machine. It simply prints two copies of its input. We’ll place it behind H. Here’s another simple machine. We call this one – the Negator. When the Negator receives the words “not stuck”, it gets stuck. And when it receives the words “stuck”, it does not get stuck . . . and it prints a smile. We’ll place it in front of H. Let’s wrap it all in a neat package we call: the X machine. X has one input, and one output. Let’s draw its blue print. As before, this blue print fully defines X. What do you think will happen if we feed X with its own blue print? Will it get stuck? Let’s find out. P . . . simply duplicates our input. H receives two copies of the blue print of X. It should now determine what happens when X is fed with its own blue print. Let’s assume it says . . . not stuck. N negates that, and gets stuck. So feeding X with its own blueprint causes it to get stuck. But H said it wouldn’t. H was wrong. Let’s try again. This time we’ll assume H says “stuck”. X didn’t get stuck - but H said it would. H was wrong again. But H is supposed to always be right . . . This is a contradiction, . . . proving H cannot exist.
