-5
$\begingroup$

Let HALT be a program that can decide the halting problem for any program and its input. HALT has two inputs, the program and the program's input. Let OPPOSITE be a program that accepts a program as input, calls HALT with its input as both of HALT's inputs, and then does the opposite of whatever HALT has concluded. If we imagine running OPPOSITE(OPPOSITE), then the result is supposed to show a contradiction. Let's assume anyone using such logic will come to the same conclusion.

Pseudocode you've surely seen before

OPPOSITE (INPUT) :
   if HALT(INPUT, INPUT) == YES :
      LOOP_FOREVER
   else 
      STOP

Since OPPOSITE runs/calls HALT, if HALT ran naively without analysis by simply running the program with its input, it would result in an infinite stack/loop without reaching a conclusion. This could prove HALT is not actually capable of deciding for all programs. However, if it does so, HALT may actually return the correct answer.

An infinite loop or an infinite stack must be detectable by HALT because this is a manner in which a program may fail to halt.

Suppose HALT runs OPPOSITE(OPPOSITE) naively without analysis. Thus the OPPOSITE run by HALT enters the infinite loop and this is detected by HALT, as mentioned above. HALT then decides to stop naively running the program at some point and in the last call returns an answer that OPPOSITE doesn't halt. The last OPPOSITE then halts. The last HALT then returns an answer that its input doesn't halt. The last OPPOSITE then attempts to run forever. The last HALT then detects the infinite loop, stops the last OPPOSITE, and returns an answer that OPPOSITE doesn't halt. ... This loops continues until the original OPPOSITE(OPPOSITE) regains execution.

Thus we have examples of OPPOSITE doing both, so no matter what the first HALT returns, it will be correct and not a contradiction.

So my question is, have I made any logical errors so far?

$\endgroup$
0

2 Answers 2

4
$\begingroup$

Yes, you seem to have made at least one error. Programs don't "know" anything. That was the first error I spotted, and then I stopped reading, as a single logical error invalidates an argument. Therefore, the statement "Let us further assume that HALT knows it can decide the halting problem" is meaningless and nonsensical.

$\endgroup$
6
  • $\begingroup$ There is an entire subfield of AI called Knowledge Representation. Its entire point is to encode knowledge. To 'know' is to hold knowledge of a set of facts. What is the problem? $\endgroup$ Commented Sep 5, 2023 at 4:16
  • $\begingroup$ I have reformulated my question to avoid unnecessary lines of thought. Please consider looking at this new formulation. $\endgroup$ Commented Sep 7, 2023 at 0:20
  • $\begingroup$ Why is my original comment gone and reformulated in the above answer? Or am I missing something? @DW did you happen to remove the comment? The OP is responding to it above, but it seems not to be available. $\endgroup$ Commented Sep 7, 2023 at 16:53
  • 1
    $\begingroup$ @Michel, I deleted a bunch of comments that were obsolete. Comments are often deleted when they are no longer relevant to the latest version of the question. See, e.g., softwareengineering.meta.stackexchange.com/a/2235/34181, meta.stackexchange.com/a/237980/160917. $\endgroup$
    – D.W.
    Commented Sep 7, 2023 at 17:57
  • 1
    $\begingroup$ "So my question is, have I made any logical errors so far?" Your descriptions are far too informal to interpret what is meant by each statement. I'm referring to the paragraph: "Suppose Halt runs ... " Even before that point, matters are not clear. I would suggest taking this off cs stackexchange and discuss with someone who is well versed in the Halting Problem. The statements are so imprecise that only a very long list of exchanges may bring some clarity. This is too labour intense for substack imo. An expert in the area will ensure you get matters clear in no time. $\endgroup$ Commented Sep 8, 2023 at 19:00
0
$\begingroup$

"So my question is, have I made any logical errors so far?" Your descriptions are far too informal to interpret what is meant by each statement. I'm referring to the paragraph: "Suppose Halt runs ... " Even before that point, matters are not clear. I would suggest taking this off cs stackexchange and discuss with someone who is well versed in the Halting Problem. The statements are so imprecise that only a very long list of exchanges may bring some clarity. This is too labour intense for substack imo. An expert in the area will ensure you get matters clear in no time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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