## Contradiction - Intro to Theoretical Computer Science

• 0:00 - 0:06
So we already know that we arrived at the contradiction. We checked that in the two quizzes, and we didn't
• 0:06 - 0:11
make any mistake here. One thing that could be wrong is that we just cannot run the program inverse halt on itself.
• 0:11 - 0:17
But again, this is perfectly fine because inverse halt is a program, and because it's a program,
• 0:17 - 0:20
we also have its source codes. So we can easily feed this program to itself.
• 0:20 - 0:25
So let's go back one more step, step number three. The program inverse halt, how we wrote that--
• 0:25 - 0:32
Did we make any mistake here? Well, no, we didn't. We just used the algorithm halt, we gave it a valid input.
• 0:32 - 0:36
So we gave it a program to check, and we gave it also an input for that program.
• 0:36 - 0:41
Sometimes it might be confusing that the program is both an input and an actual program,
• 0:41 - 0:47
but it's perfectly fine again, because the program here is the source code, so we can take it as both.
• 0:47 - 0:53
The rest of the code is fully valid, so it's deterministic, there doesn't really go anything wrong here.
• 0:53 - 0:58
So this contradiction here cannot be due to step four, it can also not be due to step three.
• 0:58 - 1:07
What about step two? Well, that there is an algorithm "halt" for the halting problem was a direct conclusion of assumption
• 1:07 - 1:17
number one. So there also cannot be something wrong with number two, unless of course number one in itself was wrong.
• 1:17 - 1:22
And since we checked two, three, and four, and there must be some sort of error in the proof,
• 1:22 - 1:28
the only place where this error can be is here in step number one. So what does step number one say?
• 1:28 - 1:33
Step number one assumed that the halting problem is in fact decideable.
• 1:33 - 1:38
And since this logically leads us to contradiction, this assumption here must be false.
• 1:38 - 1:43
So the halting problem cannot be decideable. It is in fact undecideable.
• 1:43 - 1:49
And that of course means that there's no algorithm that will tell you, for any given program, and any given input,
• 1:49 - 1:55
if that program will ever stop. Now, the technique that we used here, at least if you're not used to it,
• 1:55 - 2:02
can sometimes be a little bit confusing. I would therefore like to give you a second illustration of exactly this proof here,
• 2:02 - 2:04
just to make sure that you understand it.
Title:
Contradiction - Intro to Theoretical Computer Science
Video Language:
English
Team:
Udacity
Project:
CS313 - Theoretical Computer Science
Duration:
02:05
 Udacity Robot edited English subtitles for Contradiction - Intro to Theoretical Computer Science sp1 added a translation

# English subtitles

## Revisions Compare revisions

• API
Udacity Robot
• sp1