1
$\begingroup$

So watching many youtube channels, the explanation to the impossibility of solving the halting problen involves assuming you can, doing the opposite, and feeding it back into itself to create a paradox.

What I don't get is why this is an (over)simplification. The logic seems to check out. What is the flaw in this reasoning?

$\endgroup$
5
  • 2
    $\begingroup$ Why do you think it's an (over)simplication? Admittedly, it's only a sentence long. $\endgroup$ – Rick Decker Jan 13 at 0:30
  • $\begingroup$ That was the disclaimer made in one (and if I recall correctly) a few others of the videos $\endgroup$ – yolo Jan 13 at 7:48
  • $\begingroup$ Though it has occured to me that similar arguments can be made for things we can make codes of. For example, assuming a code halts, I'm fairly certain we can test if a code outputs 'bird' by simulating it. In order to make it opposite we just cancel each time it attempts to make an output and output it if was never cancelled $\endgroup$ – yolo Jan 13 at 8:03
  • $\begingroup$ "...and output it if it was never cancelled." Suppose the program being simulated got into an infinite loop? You'd never get an answer. $\endgroup$ – Rick Decker Jan 14 at 14:21
  • $\begingroup$ It occurred to me recently that it requires a code to simulate. So if you input its own code, it quite literally wouldn't work due to lack of an input; I would guess that this would apply to any complete class of problems relating to the analysis of code. $\endgroup$ – yolo Jan 14 at 15:00
1
$\begingroup$

It's basically correct, but it can be viewed as an oversimplification because that one sentence doesn't explain the details of how to feed it back into itself or why "feeding it back into itself" creates a paradox -- that requires additional explanation or justification.

$\endgroup$
2
  • $\begingroup$ The videos go on to explain why a paradox is caused, but I'm not quite sure what more there can be to 'feeding it back into itself'. Could you elaborate on this please? $\endgroup$ – yolo Jan 13 at 8:53
  • $\begingroup$ @yolo, one has to explain exactly how that should be done. It's not trivial. Usually it requires some code to specify how that is to be done. $\endgroup$ – D.W. Jan 13 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.