Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← 05-53 Infinite Loop Solution

dummy description

Get Embed Code
3 Languages

Showing Revision 1 created 05/13/2012 by Amara Bot.

  1. Going through it together, vladimir immediately returns 1,
  2. so it halts in pretty much 1 step.
  3. So yes, this does not loop forever.
  4. To figure out the value of nabokov, we call nabokov,
  5. which causes us to call nabokov, which causes us to call nabokov.
  6. This is one of those infinite loops.
  7. Not my most symmetric infinity symbol ever.
  8. We never actually get a value out of this.
  9. We call ourselves over and over again.
  10. This procedure does not halt.
  11. You might be thinking, "Oh, eventually we will run out of stack space,"
  12. or more prosaic concerns like that, but remember here
  13. I want you to think in the abstract.
  14. We're assuming this mythical halts procedure.
  15. How about pale? X is 0, while True, x is x + 1.
  16. We actually looked at this before.
  17. This loop does not halt, does not terminate.
  18. How about fire?
  19. We start out with x is 0 and y is 1000,
  20. and as long as x is less than y, we add 2 to x and we add y to 1.
  21. After a little bit, this will be 2 and 1001, then this will be 4 and 1002,
  22. this will be 6 and 1003.
  23. And although it doesn't look like it now, eventually x will catch up to y
  24. because x is growing twice as fast.
  25. For example, after 1000 steps, x will be 2000 and y will also be 2000,
  26. at which point we'll break out of this loop.
  27. So fire does in fact halt.
  28. Pale Fire was a 1962 novel by Nabokov.
  29. He's perhaps more famous for Lolita.
  30. He was a Russian author who did a lot of writing in English.
  31. All right. We didn't see anything bad. That all looked fine.
  32. We could figure out just by staring at things whether they halted or not.
  33. Why am I predicting doom and gloom? We didn't have any problems.