Return to Video

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

English subtitles

Revisions Compare revisions