Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?



share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.