## Logic Crash - Intro to Theoretical Computer Science

• 0:00 - 0:06
So far, all is good. But now I'm going to do the sneaky thing that I did in the last proof:
• 0:06 - 0:11
I'm going to put inverse halt into this list of programs. So if inverse halt is run on itself,
• 0:11 - 0:16
there can only be two cases, right? So, halt can either say yes or no.
• 0:16 - 0:20
We know it has to be one of the two cases, because there's no other possibility.
• 0:20 - 0:26
Now, just as above here, what would that mean? So if halt, on inverse halt and inverse halt, would say yes,
• 0:26 - 0:34
that would mean that inverse halt--and I'm just going to write it like this, so inverse halt stops, given inverse halt as an input.
• 0:34 - 0:38
And the other case, of course, would mean that inverse halt does not stop, given itself as an input.
• 0:38 - 0:45
So this is what happens if we read the table in this way. Now, let's read it another way because what we noticed here is that,
• 0:45 - 0:52
if the program stops when it's given itself as an input, inverse halt on this program should go into an infinite loop.
• 0:52 - 0:57
In other words, if we transfer what we did here to down here, we would have to write the following.
• 0:57 - 1:02
So now let's compare those two statements in this line here. And here we said inverse halt will go into an infinite loop
• 1:02 - 1:09
when given inverse halt, which is just itself, as an input. So you have the same contradiction here as we had in the other proof.
• 1:09 - 1:14
And of course, the same thing is true down here. So here we said inverse halt does not stop, given itself as an input.
• 1:14 - 1:21
And here we said inverse halt does stop when given itself. So this table here is a nice way to introduce the kind of logic crash
• 1:21 - 1:27
that we use in the proof by contradiction. Because there's two ways of constructing this table.
• 1:27 - 1:33
So the first way is to construct it this way, basically. Meaning that we look at what halt says--either yes or no--
• 1:33 - 1:39
so we arrive at the conclusion of what the program does, based on what halt has to say about that program.
• 1:39 - 1:44
Now, the other way of constructing this table is more or less going this way.
• 1:44 - 1:51
So, based on what halt will say that the program does, we can predict the behavior of inverse halt.
• 1:51 - 1:57
And this construction works perfectly fine. So constructing it this way or this way, those are both compatible views.
• 1:57 - 2:03
With one exception: Once we feed inverse halt into this table, these two logics crash,
• 2:03 - 2:10
because the conclusions that we draw in this way are exactly the opposite of the conclusions that we draw in this way.
• 2:10 - 2:15
And that is why the contradiction is happening. And actually, constructing the table this way or this way is perfectly fine.
• 2:15 - 2:18
The only problem is making the assumption that this halt algorithm here actually exists,
• 2:18 - 2:20
which you already know it doesn't.
Title:
Logic Crash - Intro to Theoretical Computer Science
Video Language:
English
Team:
Udacity
Project:
CS313 - Theoretical Computer Science
Duration:
02:21
 Udacity Robot edited English subtitles for Logic Crash - Intro to Theoretical Computer Science sp1 added a translation

# English subtitles

## Revisions Compare revisions

• API
Udacity Robot
• sp1