
So we already know that we arrived at the contradiction. We checked that in the two quizzes, and we didn't

make any mistake here. One thing that could be wrong is that we just cannot run the program inverse halt on itself.

But again, this is perfectly fine because inverse halt is a program, and because it's a program,

we also have its source codes. So we can easily feed this program to itself.

So let's go back one more step, step number three. The program inverse halt, how we wrote that

Did we make any mistake here? Well, no, we didn't. We just used the algorithm halt, we gave it a valid input.

So we gave it a program to check, and we gave it also an input for that program.

Sometimes it might be confusing that the program is both an input and an actual program,

but it's perfectly fine again, because the program here is the source code, so we can take it as both.

The rest of the code is fully valid, so it's deterministic, there doesn't really go anything wrong here.

So this contradiction here cannot be due to step four, it can also not be due to step three.

What about step two? Well, that there is an algorithm "halt" for the halting problem was a direct conclusion of assumption

number one. So there also cannot be something wrong with number two, unless of course number one in itself was wrong.

And since we checked two, three, and four, and there must be some sort of error in the proof,

the only place where this error can be is here in step number one. So what does step number one say?

Step number one assumed that the halting problem is in fact decideable.

And since this logically leads us to contradiction, this assumption here must be false.

So the halting problem cannot be decideable. It is in fact undecideable.

And that of course means that there's no algorithm that will tell you, for any given program, and any given input,

if that program will ever stop. Now, the technique that we used here, at least if you're not used to it,

can sometimes be a little bit confusing. I would therefore like to give you a second illustration of exactly this proof here,

just to make sure that you understand it.