YouTube

Got a YouTube account?

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

English subtitles

← 20-06 The Halting Problem

Get Embed Code
1 Language

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

  1. So can a computer solve any problem that meets these 3 requirements?
  2. It seems, in a way, like a computer should be able to do that, doesn't it?
  3. I mean, the input is fit for a computer; the output is fit for a computer.
  4. We have even been very, very nitpicky with finite strings, constant number of symbols,
  5. and we want an objectively correct and definitive answer.
  6. No grading student's essays, no predicting the future,
  7. no looking at pictures and telling us if they're beautiful.
  8. I'm now going to show you a problem that meets these 3 criteria.
  9. I will also be able to show you that no computer can ever solve it.
  10. And this is actually a problem where it would be
  11. very useful to have a computer being able to solve it.
  12. So I guess you've all been in this situation here where on your computer,
  13. you're working, and you've just started a certain type of calculation or task on the computer.
  14. The computer tells you yes, I'm 10% done, and after a while this moves to 20%,
  15. after a while it moves to 30%, and, of course, pending on what system you're working on,
  16. your mouse turns into this hourglass here, and now the progress bar gets stuck.
  17. And it stays there. You go have lunch, you come back, and it stays there.
  18. So the question is, at some point in time--I mean, you want this task to get done--
  19. but maybe in the next minute the computer will go on.
  20. Maybe it's just thinking, it's just working, but it could also be that your program has crashed.
  21. If your computer stays that way for quite a time, well, you probably would assume
  22. that it has crashed, but you never know for sure.
  23. So what if we had an algorithm for that?
  24. What if we had an algorithm that took as input a computer program, P.
  25. It could be written in any language, basically.
  26. So Python, C++, Java, or whatnot. And, of course, we also wanted input for that program.
  27. And the input, of course, in accordance with rule number 1,
  28. will be a finite string using a constant number of symbols.
  29. And actually, the program, of course, will be as well.
  30. So it may be, for example, the source code of a program.
  31. We want this algorithm to tell us if we run the program on the input,
  32. does the computer ever finish, or does it go into an infinite loop?
  33. Very simple question. And, of course, this problem totally conforms with all 3 requirements here.
  34. So as I just said, the input is a finite string, constant number of symbols, perfect.
  35. Output, it's a decision problem so the output will either be yes or no.
  36. And, of course, the output is also objectively correct, because
  37. we're talking about deterministic machines here, so you can easily check
  38. if the program, indeed, will go into an infinite loop,
  39. if the computer tells you where the problem is.
  40. And this problem is known as the famous, and it's really famous, halting problem.