Return to Video

22x-07 Decisions

  • 0:00 - 0:02
    Now let's talk about decidability.
  • 0:02 - 0:08
    I'd like you to tell me which of the following statements are actually decidable
  • 0:08 - 0:10
    and check whichever ones are.
  • 0:10 - 0:14
    The first one is given a program P and an input I,
  • 0:14 - 0:18
    P produces I as its output.
  • 0:18 - 0:23
    The second statement is given two programs, they will always produce the same output
  • 0:23 - 0:25
    for a given input.
  • 0:25 - 0:30
    The third is given a program P and input I, P uses at most 50KB of memory.
  • 0:30 - 0:35
    Next, given a program P that takes 2 arbitrary integers as input,
  • 0:35 - 0:40
    we determine if P outputs the sum of these numbers.
  • 0:40 - 0:45
    Finally, given a graph with N vertices, determine if it has a clique of size at least k.
  • 0:45 -
    Check all that you think are decidable.
タイトル:
22x-07 Decisions
Team:
Udacity
プロジェクト:
CS313 - Theoretical Computer Science
Duration:
0:49
Amara Bot added a translation

English subtitles

改訂