# Confusion of halting problem

Show that the following problem is solvable.Given two programs with their inputs and the knowledge that exactly one of them halts, determine which halts.

lets P be program that determine one of the program will be halted.

P(Program x,Program y){

if(x will be halted)

then return 1;

else

then return 2;
}


since we know that exactly one of them will be halted,if 1 then program x will be halted.Otherwiae program y will be halted.

then we construct a new program call D

D(X,Y){

if(P(X,Y) == 2)

D will halt;

else

while(1)//D will not halt;

}


lets S be aritbrary program.

So if we have D(D,S)

if D will halt then D will not halt

if D will not halt then D will halt

It impiles a contradiction same as halting problem.

But the question stated that it is solvable.

• What if $P(X,Y)$ never terminates? How does $P$ compute "$x$ will be halted" in the if statement? – Andrej Bauer Jul 7 '20 at 16:08
• assume that p must return a result.because P is program that determine one of the program will be halted.I try to construct a counterexample similar as halting problem. – Moly Holy Jul 7 '20 at 16:14
• @Andrej Bauer because wiki also construct the counterexample for halting problem like that...so It assume the program exist and it can determine the program halt or not. – Moly Holy Jul 7 '20 at 16:30
• So you have shown: if $P$ correctly determines whether $x$ halts then there is a contradiction. The conclusion is: $P$ does not correctly determine whether $x$ halts. And you are not any closer to the solution to your problem. – Andrej Bauer Jul 7 '20 at 16:31
• Let me give you a hint: run both $x$ and $y$ in parallel. – Andrej Bauer Jul 7 '20 at 16:32

To start with an important side note: what are the inputs for $$X$$ and $$Y$$ that they will halt on? you need to specify a specific input for the machines in order for the question to be well-defined (for example, the question could be "given $$X,Y$$ where exactly one terminates on $$\epsilon$$, find who halted." Or maybe, "given ... where exactly one always halts on itself as an input...")

I see what confused you there. The problem is indeed solvable: in $$P$$ emulate both $$X$$ and $$Y$$ and answer whoever halted first.

The problem in your solution is that an input to $$P$$ must be $$X,Y$$ where exactly one of them halts, and the other doesn't.

So, a proper input to $$D$$ must be a proper input to $$P$$. Now notice you called $$D(D,S)$$. To make sure that $$D$$ will return a correct output, we must have proper inputs: only one of $$D$$ or $$S$$ halts! But... If $$S$$ halts then your $$D$$ also halts and this is not a proper input to $$P$$, and therefore also not a proper input to $$D$$. Thus you cannot rely on output from $$D(D,S)$$ as it may not be correct

• thanks but why "If S halts then your D also halts",I don't get it – Moly Holy Jul 8 '20 at 19:15
• Because we assumed $D,S$ are proper input to $P$ (and would get a contradiction later) and thus $P(D,S)$ halts and returns 2 (as we assumed $S$ halts. If it doesn't, then $D$ halts and try to think of a similar argument). Since $P(D,S)=2$, then by definition of $D$ we get that $D$ halts! – nir shahar Jul 8 '20 at 20:02
• Thanks, I maybe get it.We first assume D,S are proper input to P,but in the end we always find out that D S both halt or D S both not halt So they are not the proper input to P,so function P can not be established,can I conclude like that? – Moly Holy Jul 9 '20 at 4:44
• Yes. This is the idea for the reasoning why $D$ doesn't create a contradiction (except for that your "halting" statement plus this one do show that $P$ cannot be created unless we assume proper inputs) – nir shahar Jul 9 '20 at 6:35
• Essentially, this means that $P$ is not solvable unless you assume proper inputs (one halts and the other doesnt). Therefore, in $D$ you must make sure to give $P$ proper inputs, but as we have seen - $D$ doesn't satisfy this rule – nir shahar Jul 9 '20 at 6:41