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?

Almost

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.

StackExchange Computer Science Q#70212, answer score: 4