Is the following function $$g(x) = \begin{cases} 1 & \mbox{if } \phi_x(x) \downarrow \mbox{or } x \geq 1 \\ 0 & \mbox{otherwise } \end{cases}$$ computable?
Please note that $\phi_i(x) \downarrow$ means that the function with index $i$, converges on input $x$.
Let there exist $i \in \mathcal{N}$ such that such that $\phi_i \simeq g$. By the s-m-n theorem $\phi_i (x) \simeq \phi_{s_1^0(i)}(x)$ and $\simeq \phi_p(x)$ for some $p$, by the fixed point theorem, being $s_1^0(i)$ a total computable function not depending on anything, because $i$ is fixed. Now, consider $g(p)$. As $\phi_{p(x)} \downarrow$ for all $x \geq 1$, $g(p) = 1$ if and only if $\phi_p(p) \downarrow$ by the definition of $\phi_p$, which is actually the function $g$. Hence, if $g$ would be computable, the halting problem would be computable as well. Therefore, we reach a contradiction.
I came up with this solution, but I don't know whether it is correct. Particularly, I don't know whether I can use the s-m-n theorem if either $m$ or $n$ is $0$. Any ideas whether my solution is correct, and if not how to solve it?
Best Answer
This function is computable. Clearly (by the definition of $g$) we have $g(x) = 1$ for all $x \geq 1$. Also $g(0)$ can be either $0$ or $1$. Regardless, this function is computable: in the latter case it is the constant function $g(x) \equiv 1$ and in the first case it is the charateristic function of the set of positive numbers $g(x) = \text{sg}(x)$, which is recursive.
Alternatively, this function differs from (trivially computable) the constant $1$ function at most in one point $x = 0$. It is quite easy to show that if you change the values of some computable function in finite number of points you obtain the function which is also computable.
This exercise shows that trivially computable functions can be defined using some intricate set of instructions. Another well-known example of such a function is: $$f(x) = \begin{cases} 1, & \text{if a consecutive run of at least $x$ $9$'s occurs in the decimal expansion of $\pi$,}\\ 0, & \text{otherwise.} \end{cases}$$
It is either the constant $1$ function or equals $1$ at the finite initial segment of $\mathbb{N}$ and hence differs from the constant $0$ function only at the finite number of points.
One more example: $$f(x) = \begin{cases} 0, & \text{if $\mathsf{ZFC} \vdash P \neq NP$,}\\ 1, & \text{if $\mathsf{ZFC} \vdash P = NP,$}\\ 2, & \text{otherwise.} \end{cases}$$
We don't know which of the cases takes place, but in any of them the resulting function is computable. At the present time we don't have an algorithm to compute this function, but it is still computable. So all these proofs are non-constructive.