## Subtitles section Play video

• 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 onethe Negator.

• When the Negator receives the wordsnot stuck”, it gets stuck.

• And when it receives the wordsstuck”, 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 saysstuck”.

• 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.

This is computing machine A.

Subtitles and vocabulary

Click the word to look it up Click the word to find further inforamtion about it

# Proof That Computers Can't Do Everything (The Halting Problem)

• 24 0
許祐綸 posted on 2022/01/20
Video vocabulary