Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.