# Rice's Theorem for Total Computable Functions

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?

• 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. ​ ​ ​ ​ ​ ​ ​
– user12859
Feb 12 '17 at 15:28
• @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. Feb 12 '17 at 15:46
• 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}$. 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:
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.