3

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?

  • Does "converges" in this context mean "halt"? – Eli Rose Jan 04 '16 at 15:41
  • @EliRose Yes, exactly. –  Jan 04 '16 at 15:42
  • What is $h$? You also seem to treat $p$ as a function at one point. What function is it? – Wojowu Jan 04 '16 at 18:35
  • @Wojowu Sorry, it was a typo, it is actually $g$. I edited my answer. Regarding the $p$, I used a similar argument that I had in my lecture notes, which said: "$s_1^1(t,x)$ is a function only depending on the argument $x$ (note that $t$ is fixed) and hence it can be written as $f(x)$. By the fixed point theorem we get $\phi_{f(p)} \simeq \phi_p$". The problem is that I don't know whether I can use the s-m-n theorem if either $m$ or $n$ is $0$. And if I can, how should it look like exactly? –  Jan 04 '16 at 19:00
  • S-m-n theorem requires $m, n > 0$. What is the reasoning behind applying the fixed point theorem here? You have that for some fixed $i$ it holds that $\phi_i \simeq g$ and after that you use the FP-theorem to obtain some (again fixed) $p$ with the same property. – Random Jack Jan 04 '16 at 21:32
  • @RandomJack I followed a similar example that I had, but in that one the function took two inputs, so one could apply the s-m-n theorem. But, seems like as you pointed out in my problem I cannot apply s-m-n theorem. Any ideas how to solve this problem? –  Jan 04 '16 at 21:35

1 Answers1

1

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.

Random Jack
  • 2,906
  • Thanks for the great answer. One question, about which characteristic function are you talking in the first paragraph, with $sg(x)$? –  Jan 05 '16 at 19:24
  • 1
    You're welcome. The characteristic function of the set $\mathbb{N}_+ = {1, 2, 3, \dots}$. As far as I know this is a standard notation (also known as signum function): $$\mbox{sg}(x) = \begin{cases} 0, & \mbox{if } x = 0,\ 1, & \mbox{otherwise}. \end{cases}$$ – Random Jack Jan 05 '16 at 20:25