Fix a Gödel numbering, and write $\phi_n$ for the function coded by $n$. Rice's theorem states that if $P$ is the set of partial computable functions, and $A \subseteq P$, then the decision problem

Given $n$, does $\phi_n \in A$?

is decidable if and only if $A = \emptyset$ or $A = F$; that is, if the decision problem always has the same answer.

Now consider the set $T$ of total computable functions instead. Clearly, the problem

Given $n$ with $\phi_n \in T$, does $\phi_n \in A$?

is no longer decidable if and only if $A \in \{\emptyset,T\}$. In fact, for recursive set $M\subseteq \mathbb N^k$, the problem is also decidable for $$ A_M = \{\phi_n \in T \mid (\phi_n(0),\ldots,\phi_n(k-1)) \in M\}. $$ So is it true that the problem is decidable if and only if $A$ is of the form $A_M$ as above? If not, can we give a different restriction on the form of $A$ that does give us a theorem?

  • 1
    $\begingroup$ Even for just decidable subsets of $\mathbb{N}$ (equivalently, total functions to {0,1}), they still don't have to be of that form: ​ ​ ​ Choose computable infinite binary tree with no computable infinite branch, pick a computable subset M of $\mathbb{N}$ which is neither finite no co-finite, pair-off the $\mathbb{N}$ to convert the input function to a function from $\mathbb{N}$ to {0,1,2,3}, and accept-or-not according to whether [the input natural at which the input function stops following the tree] is in M or not. ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Feb 12 '17 at 15:28
  • $\begingroup$ @RickyDemer, thanks for the nice example! I am particularly interested in the other side; are there simple-ish restrictions on $A$ which ensure that the problem is not computable? Edit: for example, it seems clear to me that $A = \{\phi_n \mid \exists k(\phi_n(k) = 0)\}$ ought to be non-computable, but I don't have a very simple criterion why. $\endgroup$ – Mees de Vries Feb 12 '17 at 15:46
  • $\begingroup$ Your sets $A_M$ are not closed under unions, but decidable subsets are, so at the very least you need to close under finite unions. But as @RickyDemer points out, that's not enough. And since the spaces of total computable functions into $\{0, 1\}$ and into $\mathbb{N}$ are computably isomorphic (even computably homeomorphic), his example can be translated to one on total functions into $\mathbb{N}$. $\endgroup$ – Andrej Bauer Sep 20 '17 at 23:17


The correct answer is that a property of recursive languages is r.e. if and only if it can be verified by a finite number of values (though unlike in your example the exact number of values can be unbounded, so $k$ can depend on $n$). In fact, the wikipedia page for Rice's theorem has a section on this:

...the analogue says that if one can effectively determine for every recursive set whether it has a certain property, then only finitely many integers determine whether a recursive set has the property.

More precisely, a property is r.e. iff there is a r.e. set $T_1$ with the prefix property (i.e.- no string in $T_1$ is a prefix of another) such that $\phi_n$ has the property iff there is some $k$ such that the sequence $\phi_n(0), ..., \phi_n(k-1)$ is in $T_1$ (we can make sense of a sequence being in a set of natural numbers by encoding this as $p_1^{\phi_n(0)}\cdot p_2^{\phi_n(0)}\cdot ...\cdot p_{k}^{\phi_n(k-1)}$ where $p_i$ is the $i$th prime). A property would be recursive iff it is r.e. and co-r.e.

This pretty much says that we can get no more information out of the index $n$ than the function $\phi_n$ itself, because any computable property must be computable only using calls to the function $\phi_n$. This may sound trivial, but it is no means obvious since a priori the input $n$ might have some extra non-syntactic information computably nestled into it.

Rice's theorem essentially states that no extra non-syntactic information about partial recursive functions can be computably nestled into their Godel encodings. As it turns out this is also equivalent to the above characterization, so the same thing holds for total functions as well. I suppose one could make this statement even stronger by generalizing to even more general classes of functions, but I do not know if this is true.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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