Computing non-halting inputs of semantic non-equivalent programs

Question

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?

Answer 1

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.