# Proving uncomputability — Rice's theorem

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

-
I assume $n>0$ for all $n$, then, so $f(x)=0$ means explicitly that it never converges. Or maybe you want $1+\min n$...? – Thomas Andrews Dec 20 '12 at 17:47
Yes, $n > 0$; sorry for the ambiguity – Trin Dec 20 '12 at 17:48
It's true either way, of course, just makes the set slightly different if $n=0$ is allowed. – Thomas Andrews Dec 20 '12 at 18:04

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.