Confusion of halting problem
-
29-09-2020 - |
Question
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.
Solution
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