1
$\begingroup$

I am trying to prove the uncomputability of the following function: Let $\varphi$ be a Gödel-numbering of the computable functions. Consider the following function:

\begin{align*} f(x) = \left\{ \begin{array}{l l} \mathrm{min}\ n \text{ among } \varphi_x(n) \downarrow & \quad \text{if $\exists n\ \varphi_x(n) \downarrow$}\\ 0 & \quad \text{otherwise} \end{array} \right. \end{align*}

Now this function is obviously not computable. My question now is whether the following argument is correct: Consider the following function:

\begin{align*} g(x) = \left\{ \begin{array}{l l} 1 & \quad \text{if $f(x) \neq 0$}\\ 0 & \quad \text{otherwise} \end{array} \right. \end{align*}

If $f$ was computable, $g$ would be computable too. Hence, the set $\{x\,|\,g(x) = 1\}$ would be recursive. Is this a correct conclusion and if yes, can I then apply Rice's theorem to obtain the non-decidability of the set and hence, the uncomputability of $f$. Or: is there a better way to obtain a proof of the uncomputability of $f$?

TIA

Trin

  • 0
    It's true either way, of course, just makes the set slightly different if $n=0$ is allowed.2012-12-20

1 Answers 1

1

Yes, that looks right.

I would personally avoid introducing $g$, which doesn't actually do much, and just write:

The value of $f(x)$ clearly depends only on $\varphi_x$ (every $x$ in the definition of $f(x)$ appears as a subscript to $\varphi$), so $\{x\mid f(x)=n\}$ is extensional for every $n\ge 0$. Since it is also obviously non-trivial for every $n$, Rice says it cannot be computable. But it would be easily computable if $f$ was, so $f$ isn't.