English subtitles

← 21-08 Statement Of Rice's Theorem

Get Embed Code
1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. Now, what is Rice's theorem?
  2. Rice's theorem is actually quite simple.
  3. Rice's theorem simply says that if you asked for an algorithm
  4. to decide the program has a functional property and it can be any functional property,
  5. then, you're looking at an undecidable problem.
  6. I don't even know, that come out of surprise to you
  7. after we have shown that basically anything is undecidable.
  8. It's almost a surprise now that any problem on a computer
  9. should even be solvable but we'll get into that in a minute.
  10. The main question, of course, how can you show Rice's theorem,
  11. and the proof that is actually easy and it follows the same scheme as above here.
  12. So the proof of this general statement
  13. follows the same scheme that all of our other proofs of undecidability have basically used.
  14. So, again, we assumed that there is a program that can decide
  15. for another program if that possesses a certain functional property.
  16. So we're given a program P again, any program P,
  17. and we assumed that no matter what P is,
  18. we can always say "does P have a functional property?"
  19. Now, on the other side, assume that there is another program P',
  20. and what we want to do is solve the halting problem for this program here
  21. and then we'll use the algorithm here that can decide for any program P
  22. if it has a functional property to solve the halting problem
  23. and the way we do this is as follows:
  24. We construct a new program we will call program X and this program has only 3 steps.
  25. First, it runs P' then it clears all of the memory,
  26. so basically a fresh start of a machine,
  27. and this is the only reason why we need this condition too here for a functional property
  28. because if we have an algorithm that can decide a functional property,
  29. this means that there are some programs that has this property and others that don't.
  30. So, we will now add to our program X a program that has this functional property.
  31. So, run program with functional property,
  32. and what then do is we take this program X and fitted into this algorithm here.
  33. what you can see now is the following:
  34. If P' here, the problem for which we want to solve the halting problem,
  35. runs smoothly and terminates,
  36. then this program X will have the functional property that we can decide
  37. because it runs this algorithm here and it clears the memory
  38. and then it runs the program with that functional property.
  39. This is also the reason why time is not a functional property.
  40. That would kind of destroy the proof of Rice's theorem.
  41. But if time is not an issue, then as long as P' finishes,
  42. the program X will have the functional property that we can decide here.
  43. If, on the other hand, P' goes into an infinite loop,
  44. then the program does not have the functional property
  45. because it will never be able to reach these two lines here.
  46. So, deciding the functional property for this new program X here
  47. is the same as solving the halting problem for the original program that we started out.