Donald Hoffman

My head hurts too thinking about these things.

Well, so the standard story that you'd – if you take a computer science class and –

study of the theory of computation, they'll tell you about something called the halting problem.

This is one of the big problems.

Turing, I believe, posed it and showed that it was not computational.

The question is this.

A universal Turing machine is like a universal computer.

You can give it a program.

Turing thought about putting a tape with some punches on it, essentially.

So you have this tape reader.

And the Turing machine would look at one square on the tape and read that symbol.

And then it would change state and then move left or right and write a symbol.

And that's all the universal Turing machine could do.

And so the question that Turing asked was, suppose we asked the question –

will the Turing machine stop after a finite number of moves?

Will it halt?

On arbitrary sets of these tapes that you're giving it, programs.

That's called the halting problem.

The question is, is there a Turing machine that can decide?

So is there an algorithm that can decide whether this Turing machine will halt or not for any particular given input?