English feliratok

← Inverse Halt Doesnt Halt - Intro to Theoretical Computer Science

Beágyazókód kérése
1 Language

Showing Revision 2 created 05/25/2016 by Udacity Robot.

  1. And the direct implication, of course, is exactly opposite to the last quiz.
  2. So if inverse halt, given inverse halt, does not stop, then this means that halt, run on inverse halt and inverse halt, did in fact say yes,
  3. because that is the only way that inverse halt can go into an infinite loop, because we know that halt is going to terminate.
  4. This is a direct consequence of assumption number two here, and there's no other way to go into an infinite loop.
  5. But again, something doesn't really seem quite right here when we dig a little deeper.
  6. So, halt running on inverse halt as the program, and inverse halt as the input, says yes.
  7. That means the following: Inverse halt as a program, when given inverse halt as an input,
  8. since halt says yes, will in fact halt. So again, we have the same contradiction here.
  9. We said that inverse halt running on inverse halt did not stop, or did not halt,
  10. and what we find is that the implication of this, though, is that inverse halt, when run on inverse halt, does indeed halt.
  11. Running the program inverse halt on inverse halt either must stop or it must not stop,
  12. but no matter which one of the two we assume, we always arrive at this contradiction here.
  13. Inverse halt on inverse halt stopping and not stopping at the same time, which just cannot be right.
  14. And having this contradiction here means that something either in the proof has gone wrong,
  15. or that we made some assumption along the way that cannot be true. So let's check them one by one.