consider $g$ and $f$ and $h$ as

$ \begin{align*} g(m) &= \begin{cases} 1 & if\;program\;m\;halts\;on\;input\;m \\ 0 & otherwise \\ \end{cases} \end{align*} $

$ \begin{align*} f(m,n) &= \begin{cases} undefined & if\;m=n \\ 1 & if\;program\;m\;halts\;on\;input\;n \\ 0 & otherwise \\ \end{cases} \end{align*} $

$ \begin{align*} h(m,n) &= \begin{cases} 1 & if\;program\;m\;halts\;on\;input\;n \\ 0 & otherwise \\ \end{cases} \end{align*} $

we have a counter example for computability of $g$ and $h$ but we don't have any counter example for $f$ and even more interesting function $f_{all}$ $$f(m,n)=\dfrac{m-n}{m-n}h(m,n)$$ $$f_{all}(m)=1-sgn(\lim_{w \to \infty}\sum_{\substack{n=0 \\ n\neq m}}^{w}(1-f(n,m)))$$

we know that if $p$ is a universal diophantine polynomial then we can represent a non-computable solution to the halting problem as follows $$ h(m,n) = sgn(\lim_{w \to \infty}\sum_{x_1=1}^{w}...\sum_{x_u=1}^{w}\dfrac{1}{1 + wp^2(m,n,x_1,...,x_u)}) $$

now the question is: are $f$ and $f_{all}$ computable?


1 Answer 1


It's easy to see that $f$ is not computable, using the padding lemma: there is a total computable function $t$ such that for all $x$, $t(x)>x$ but program number $x$ and program number $t(x)$ have the same behavior (= yield the same partial computable function).

This means that $f$ computes $g$, since we have $g(x)=f(x,t(x))$.

  • 3
    $\begingroup$ For instance, informally, $t(x)$ can be obtained from $x$ by inserting a no-op instructions. (I know that Turing machines don't have instructions, so make the corresponding translation to Turing machines.) $\endgroup$
    – D.W.
    Sep 24, 2022 at 20:28
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – D.W.
    Oct 18, 2022 at 16:52
  • $\begingroup$ I will accept your answer if you change $g(x) = f(x,t(x))$ to $g(x) = f(t(x),x)$ $\endgroup$
    – raoof
    Nov 15, 2022 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.