Donald Hoffman

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?

So can you tell the Turing machine to stop?

Is that the

Well, no.

So I should say one more thing about Turing machines.

So a Turing machine is going back and forth and changing its state.