Can we tell whether two programs both halt on some number?

55 Views Asked by At

$\Phi_x$ is the $x$-th computable function (TM, Recursive function ...)

$\Phi_x \downarrow$ shows the function with index $x$ which converges

is the below function computable?

$F (x,y) = \begin{cases} 0 \quad \exists m \quad \Phi_x(m) \downarrow and \quad\Phi_y(m) \downarrow\\ \uparrow \quad \text{otherwise} \end{cases}$

can we say by dovetailing technique we will find the "m" in a finite step?

1

There are 1 best solutions below

0
On

Yes computable functions are total so by your definition $F\equiv 0$ constant zero-function, hence computable.