English subtitles

← 20-27 Undecidability

Get Embed Code
1 Language

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

  1. Okay, so now you might be thinking--well, okay, so programs can become so complicated
  2. that no algorithm can decide whether they run infinitely or not.
  3. So is there a short program for which I could show you undecidability.
  4. Oh yes, there is such as a program--it's not very practical but it is an example
  5. for undecidability for very simple program.
  6. Here's a simple example of a problem that is actually
  7. not decidable, although it's very simple to write.
  8. So the input to that problem is an integer and we will just call that integer i
  9. and the output is the number of iterations that it takes to get to i=1 using the following two rules--
  10. If i is even, then set i to i/2 so they divide by 2. If i is odd, set i to 3i+1, just two simple rules.
  11. And so for example when you start out with i being 10, then we first apply the first rule.
  12. We get down to 5, 5 is odd so the new value is 16 and then we divide by 2, we divide by 2,
  13. we divide by 2, we divide by 2, so we have 1, 2, 3, 4, 5, 6 iterations.
  14. So i=10, then the answer is 6.
  15. So now we're going to let you play a little bit with this algorithm
  16. and then discuss the undecidability for it.