English subtitles

← 20-20 Implications Solution

Get Embed Code
1 Language

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

  1. So the first statement here is obviously not true. We have not even talked about time.
  2. We have just pondered the existence of an algorithm for the halting problem
  3. or more specifically, the non-existence of such an algorithm, and that is exactly what we have shown.
  4. We have shown that there's no algorithm that solves the halting problem
  5. if we allow that algorithm to be given any program and any input, but of course,
  6. there are specific programs for which we can use algorithms to decide if they will go into loops or not
  7. and this is for example one technique that is used in automated software testing.
  8. It's not that there can be an algorithm that solves the halting problem
  9. for specific cases or specific programs, the halting problem cannot be solved for the general case.
  10. So if say you have an algorithm that can solve the halting problem for any program,
  11. any input that you throw at it, that cannot be the case, but for specific,
  12. special cases, we haven't shown anything so far.