0
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ What if $P(X,Y)$ never terminates? How does $P$ compute "$x$ will be halted" in the if statement? $\endgroup$ – Andrej Bauer Jul 7 '20 at 16:08
  • $\begingroup$ 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. $\endgroup$ – Moly Holy Jul 7 '20 at 16:14
  • $\begingroup$ @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. $\endgroup$ – Moly Holy Jul 7 '20 at 16:30
  • $\begingroup$ 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. $\endgroup$ – Andrej Bauer Jul 7 '20 at 16:31
  • 2
    $\begingroup$ Let me give you a hint: run both $x$ and $y$ in parallel. $\endgroup$ – Andrej Bauer Jul 7 '20 at 16:32
0
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ thanks but why "If S halts then your D also halts",I don't get it $\endgroup$ – Moly Holy Jul 8 '20 at 19:15
  • $\begingroup$ 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! $\endgroup$ – nir shahar Jul 8 '20 at 20:02
  • $\begingroup$ 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? $\endgroup$ – Moly Holy Jul 9 '20 at 4:44
  • $\begingroup$ 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) $\endgroup$ – nir shahar Jul 9 '20 at 6:35
  • $\begingroup$ 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 $\endgroup$ – nir shahar Jul 9 '20 at 6:41

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.