not a computable function

Question

Define $\Phi_e^K(x)$ to be the output of the eth Turing machine that has K (the diagonal language) on its oracle tape and x on its input tape.

Is the map f: (x,e) $\mapsto$ $\Phi^K_e(x)$ a computable function?

let $\omega$ be the naturals.

recall a f: $\omega \times \omega$ $\rightarrow \omega$ is a computable function if there exists a turing machine that given input in $\omega \times \omega$ always halts and upon halting, outputs an integer in $\omega$ on its tape.

I reason that f is not a computable function since the machine that exists must carry K in its description. However K is infinite.

even if K were replaced by empty, we would still have an uncomputable function since there exists e s.t. there exists x s.t. f(x,e) never halts. since there are such turing machines (e.g. the machine that recognizes the halting problem) right?

Answer 1

Since you (like most of us) take "computable function" to apply only to total functions, your $f(x,e)$ can't be computable just because it isn't total. There are Turing machines that never halt (regardless of input or oracle), and if the $e$th Turing machine is one of those then $\Phi^K_e(x)$ will be undefined for all $x$.

Furthermore, your $f$ is not a partial computable function either. Let $e$ be such that the $e$th Turing machine, given any input $x$, passes $x$ to its oracle and outputs whatever answer the oracle gives it. In particular, if the oracle is (the characteristic function of) $K$, then this machine computes (the characteristic function of) $K$. So, with this fixed value for $e$, the function $x\mapsto f(x,e)$ is not computable. But if $f$ were even partial computable then $x\mapsto f(x,e)$, being total, would be computable. (I think this is essentially what Hanul Jeon meant by saying $f$ isn't computably enumerable, although "computably enumerable" ordinarily refers to sets, not functions.)

Answer 2

As you pointed out, the computability of $f$ implies that of a universal function $(x,e)\mapsto \varphi_e(x)$ hence $f$ is not computable. However, we can get more stronger result, that your function is not even computably enumerable.

The proof is simple, as we have an index $e$ such that $\Phi_e^K(x) = \chi_K(x)$, where $\chi_K$ is the characterisic function of the halting set. If $f$ is computably enumerable then so is $\chi_K$. However $\mathbb{N}-K=\chi_K^{-1}(\{0\})$, which implies $\mathbb{N}-K$ is computably enumerable, a contradiction.