0
$\begingroup$

So in the halting problem, there is a program that reverses the output of a program that tells if the input program halts or runs forever(I'll call it the main program further). The whole paradox is based on the fact that if we feed this "reverser" program to the main program the reverser program will be in two different states simultaneously: "halt" and "run forever". But what if we have multiple instances of the "reverser" program? One runs forever, and one halts. What am I missing?

$\endgroup$
2
  • $\begingroup$ "will be in two different states simultaneously: "halt" and "run forever"": what do you mean ? This wrong statement seems the source of your misunderstanding. $\endgroup$
    – user16034
    Commented Sep 13, 2023 at 9:06
  • $\begingroup$ Side note: it is completely ambiguous what you call the "main program" because the same sentence refers to three different programs. $\endgroup$
    – user16034
    Commented Sep 13, 2023 at 9:09

2 Answers 2

2
$\begingroup$

The main point of the halting problem is that you are running programs on deterministic machines, that means that the execution is always the same.

Given a program and an input, it either halts or it doesn't halt, there is no in between, and certainly not both at the same time.

$\endgroup$
6
  • $\begingroup$ I feel like I partially understand, but it is not intuitive. So the whole paradox is that because the system is deterministic there should be only one type of output for the reverser program and we get two? How can we even feed the reverser program to the main program if the reverser program requires input by itself? Can the system run multiple programs in parallel? $\endgroup$
    – YKY
    Commented Sep 12, 2023 at 20:10
  • $\begingroup$ Thinking about it I think I kinda start to get it. We have the reverser program as input to the main program, We provide the reverser program with a halt, so it runs forever and our main program detects it and returns "runs forever" Then ''runs forever" is passed to the reverser program and it returns halt. But because the system is deterministic two different inputs and outputs are not allowed. Correct me pls. $\endgroup$
    – YKY
    Commented Sep 12, 2023 at 20:16
  • $\begingroup$ @YKY Every "attempted halting problem solver" has its own reverser program, which it solves wrong. Each one either halts or doesn't halt. Some of them halt, some of them don't, but all of them are gotten wrong by their respective attempted halting problem solvers. $\endgroup$ Commented Sep 13, 2023 at 17:01
  • 2
    $\begingroup$ @YKY "We provide the reverser program with a halt" seems like confused language. Please try to figure out what you mean by that. Let's say we are talking about a specific halting solver here (I don't know it's source code, but let's just pretend we know one). We take the source code for the solver and we edit it slightly and we make it into a reverser program. This solver says the reverser program halts. But the reverser program doesn't halt. So the solver is wrong. That's all that the theorem says. There isn't really anything deeper than that. There's no "two different inputs" or whatever. $\endgroup$ Commented Sep 13, 2023 at 17:03
  • $\begingroup$ thanks @user253751, you definitely made it more transparent. My confusion was that we can have multiple instances running on the machine. Then there will be no logical contradiction, as one instance of a program can halt and another can run forever. $\endgroup$
    – YKY
    Commented Sep 16, 2023 at 2:14
0
$\begingroup$

Let me remind the principle of the proof:

  • Assume that we can write a program $H$ that is able to tell if any input program $I$ halts or not.

  • Using $H$, we create a program $G$ that halts if $I$ does not halt, and conversely.

  • Now we apply $G$ to itself as input ($I=G$). If $G$ halts, $H$ will say so and $G$ will not halt. Reciprocally, if $G$ halts, $H$ will say so and $G$ will not halt.

  • This creates a contradiction, so we won't be able to write $H$, nor $G$.


It is important to understand that you can easily write a program $H$ that is conclusive for some inputs $I$ (an easy example is checking the absence of loop constructs), but we are requesting a program that works on any input.

If I am right, your objection is that there could be different $H_i$ programs, with corresponding $G_i$ programs, so that the set of input programs that can be processed would be larger. In fact, this would be equivalent to a larger "metaprogram" that would collect the results of the constituent $H_i$ programs. And the proof applies identically to this metaprogram, leading to the same contradiction: it cannot conclude for itself.

$\endgroup$
7
  • $\begingroup$ Thanks for introducing notation into the topic. One H program and two Gi programs in the simplest. Like on any modern OS I can launch a dozen copies of the same python script and it can have different states given different input. One instance of G is provided to H and another instance of G launches after results of H. Would it also create a contradiction? $\endgroup$
    – YKY
    Commented Sep 13, 2023 at 10:07
  • $\begingroup$ @YKY: how would the number of instances influence the result ? Please elaborate. $\endgroup$
    – user16034
    Commented Sep 13, 2023 at 13:25
  • $\begingroup$ @YKY H and G are basically source codes - written down on paper or stored in disk files - not like running copies of programs. $\endgroup$ Commented Sep 13, 2023 at 17:06
  • $\begingroup$ @YvesDaoust I meant that it is possible on modern OS to launch many instances of the G program. One instance halts, and one runs forever. No contradiction in this because there will be no error. $\endgroup$
    – YKY
    Commented Sep 16, 2023 at 2:19
  • $\begingroup$ @YKY: why would one halt and the others not ??? This does not make sense. $\endgroup$
    – user16034
    Commented Sep 17, 2023 at 10:18

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.