4 ms·

I still don't get it.

• InclinedPlane 16y ago
  Say halting detectors exist, then you can build a looping detector trivially by merely reversing the outputs from the halting detector. You can then modify the looping detector so that it loops if it doesn't find any loops in the target program. Then you use the modified looping detector on itself. If you think about it, it can't be used on itself. Because if it says that it will loop then it will itself not loop, and if it says that it won't loop then it will itself loop. It's a logical paradox, which is also a reductio ad absurbum proof that no such thing as a halting detector can exist.
  • ireadzalot 16y ago
    Thanks.