Return to Video

Another Approach - Intro to Theoretical Computer Science

  • 0:00 - 0:04
    So let's construct a table like this. In the first column, we'll consider different programs.
  • 0:04 - 0:11
    And I'm just going to label them p1 for the first program, p2 for the second program, and so on and so on.
  • 0:11 - 0:18
    In the second column we'll then consider different cases of what halt can say with respect to that program,
  • 0:18 - 0:23
    when considering what happens if the program is run on itself.
  • 0:23 - 0:32
    So for example, we might say that for P1, halt might say yes, and for P2 it might say no when given the program,
  • 0:32 - 0:35
    and the program has an input.
  • 0:35 - 0:43
    Now, what does that mean? So if halt says yes in the first line here, it would mean that program one stops
  • 0:43 - 0:51
    when given program one as an input. And of course, similarly, if halt says no, it would mean that P2 goes into an infinite loop
  • 0:51 - 0:55
    when given P2 or itself as an input.
  • 0:55 - 1:01
    Now we're going to do a very quick quiz here, because what I would like you to think about here for P1 and P2,
  • 1:02 - 1:08
    what inverse halt, when run on that program, actually does. So what does inverse halt do when it's run on P1?
  • 1:08 - 1:11
    And what does inverse halt do when it's run on P2?
  • 1:11 - 1:15
    So does inverse halt, when run on P1, halt or go into an infinite loop?
  • 1:15 - 1:19
    And does inverse halt, when run on P2, halt or go into an infinite loop?
  • 1:19 - 1:21
    So please check the one that is correct for each one.
Title:
Another Approach - Intro to Theoretical Computer Science
Video Language:
English
Team:
Udacity
Project:
CS313 - Theoretical Computer Science
Duration:
01:22
Udacity Robot edited English subtitles for Another Approach - Intro to Theoretical Computer Science
sp1 added a translation

English subtitles

Revisions Compare revisions