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?


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.)

  • $\begingroup$ If we have K as an oracle then isn't $\chi_K$ computable? $\endgroup$ – user352102 Apr 24 '18 at 15:00
  • $\begingroup$ how about $\chi_{K'}$ where K' is K jump= $\{ e \mid \Phi_e^K(e)$ halts and accepts$\}$ $\endgroup$ – user352102 Apr 24 '18 at 15:02
  • $\begingroup$ $\chi_K$ is computable from an oracle for $K$ (as I wrote in my answer), but it is not computable. $\chi_{K'}$ is not even computable from an oracle for $K$. $\endgroup$ – Andreas Blass Apr 24 '18 at 15:41

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.

  • $\begingroup$ why is $\chi_K^{-1}({0})$ computably enumerable? If we have K as an oracle then isn't $\chi_K$ computable? $\endgroup$ – user352102 Apr 24 '18 at 14:55
  • $\begingroup$ @user352102 I mean that it is $\emptyset$-computably enumerable. I might misunderstand your question. $\endgroup$ – Hanul Jeon Apr 24 '18 at 22:05

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.