Return to Video

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.
Logic Crash - Intro to Theoretical Computer Science
Video Language:
CS313 - Theoretical Computer Science
Udacity Robot edited English subtitles for Logic Crash - Intro to Theoretical Computer Science
sp1 added a translation

English subtitles

Revisions Compare revisions