# Are these functions computable?

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?

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))$$.
• 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.)
• I will accept your answer if you change $g(x) = f(x,t(x))$ to $g(x) = f(t(x),x)$ Commented Nov 15, 2022 at 13:08