# Computing non-halting inputs of semantic non-equivalent programs

Let P and Q be two programs take one natural number as input and produce no output and they are not semantically equivalent, that is, there exists at least one input value n such that either P(n) halts or Q(n) halts, but not both.

Is determining one such n incomputable for arbitrary P and Q?

It can't be done by trivial dovetailing.

EDIT:

My tentative answer is that it's incomputable in the general case. Proof:

Let P be an interpreter for a reference Universal Turing machine that evaluates the input k as a program and thus halts if and only if k halts, let be Q: "if k == n then halt, else P(k)" where n is the encoding of a program that does not halt and such that there is no proof (given a formal system) that n does not halt. Then P(n) and Q(n) behave differently, but a Turing machine can never prove it.

I'm a bit puzzled by this proof because we can't explicitly construct Q, but I guess it's still sound, isn't it?

• This is not a research-level question, please move to cs.stackexchange.com. Commented Sep 4 at 15:34
• look up "Rice's Theorem" Commented 2 days ago

Assume you fix two arbitrary TMs $$P$$ and $$Q$$ such that there is some input $$n$$ for which $$P(n)$$ halts and $$Q(n)$$ does not. Then there is always a Turing machine that computes a value in which $$P(n)$$ halts and $$Q(n)$$ does not: the machine that outputs the constant $$n$$. So this is a counter example to your proof.

However, phrasing your question as follows:

Let $$M(x,y)$$ be the following function: it is only defined if $$x,y$$ are both codes for Turing machines (let's call them $$\phi_x, \phi_y$$) which do not halt on the same inputs. In these cases, $$M(x,y)$$ is actually a value on which only one of $$\phi_x, \phi_y$$ halts. Is the function $$M(x,y)$$ computable?

Then the answer is No, because the halting problem can be solved using $$M$$:

Assume $$M$$ is computable. Then there is a Turing machine that, on input $$x$$, operates as follows. It rejects $$x$$ if it does not code a Turing machine. Otherwise, it runs both $$M(x, a)$$ and $$M(x,b)$$ "simultaneously" (dovetailing), where the codes $$a$$ and $$b$$ are chosen so that $$\phi_a$$ halts on input 0 and otherwise simulates $$\phi_x$$, and $$\phi_b$$ does not halt on input 0, and otherwise simulates $$\phi_x$$. Now note that exactly one of these computations must halt, and this tells you whether $$\phi_x$$ halts on input 0 or not.

New contributor
steef is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• Thanks for your answer, but I don't think it works: if $\phi_x$ halts on input 0, then $\phi_x$ and $\phi_a$ are equivalent and therefore M(x,a) is undefined, vice versa if $\phi_x$ does not halt on input 0 then $\phi_x$ and $\phi_b$ are equivalent and therefore M(x,b) is undefined. Commented Sep 4 at 15:09
• You are right that only one of these computations halts, but this is why the machine runs the computations "in parallel", and halts as soon as either $M(x,a)$ or $M(x,b)$ halts. "In parallel" can be formalized using dovetailing you mentioned (or first running one step for the first, then one for the second, one for the first, et cetera.) Because we know that only one of the computations will halt, as soon as the machine finds that one of the two halts, it knows whether $\phi_x(0)$ halts or not and can thus give the answer. So the machine I defined always halts. Commented 2 days ago