Is there a formulation of Rice's Theorem that does not involve admissible (or Gödel) numberings?

Question

It is an easy task to devise an encoding for a computing formalism (such as Turing Machines) that has a function with fixed encoding. That is, the encoding is a numbering $\psi : \mathbb{N} \rightarrow \textbf{P}^{(1)}$ where $\textbf{P}^{(1)}$ is the set of partial unary computable $\mathbb{N} \rightarrow \mathbb{N}$ functions. By a function with fixed encoding we mean a function $f$ that has exactly one $c$ such that $\psi (c) = f$. It is also simple to have such a numbering be realizable, that is, its codes can be decoded and executed by a universal computer, and furthermore it is possible to directly provide a code $u$ for a universal computer.

It seems we have all the ingredients to falsify Rice's Theorem; since there is only one code for $f$, deciding if a function belongs to $\{f\}$ is a simple matter of checking if the function's code is $c$. At this point we must stop and check the theorem's formal statement, in somewhere such as Wikipedia, where we find out that our numbering has to admissible. The proposed numbering is obviously not so; there is no computable function that could map exactly all standard codes for $f$ into exactly $c$.

But that does not mean $\psi$ is an undesirable numbering. On the contrary, i'd argue that having a numbering where a function is restricted to a special code could be a more pleasant evironment to program in, and while i've only spoken of fixing an encoding for a single function, it should be generalizable to finite amounts of functions, and there might even be infinite classes as well (but that's a question for another TCS.se post). It's also clear that most properties over $\textbf{P}^{(1)}$ are still undecidable even under $\psi$, which suggests a more general restatement of Rice's Theorem.

My question is: Are there generalizations of Rice's Theorem that account for realizable numberings, not just admissible ones?

Answer 1

tl;dr:

(1) While (a) there is a kind of Rice's Theorem for your example construction, (b) it seems to me unlikely that one holds for realizable numberings in general.

(2) Your particular construction of a code $\psi$ with a fixed encoding for some $f$ has lots of (provable) deficiences, and I think other numberings can only get worse from there, so I don't think it's a very good programming environment, though I suppose that's a matter of what you're willing to trade off in order to have that fixed encoding.

Elaboration:

(1a) Rice-type theorem for your example construction. Let $\psi$ be the encoding from the comments, namely $\psi_0$ is the all-zeros function, and $\psi_n = \varphi_b + \delta_a$ where $n = (a,b)$ under some fixed computable bijection $\mathbb{N} - \{0\} \to \mathbb{N}^2$, $\varphi$ is a standard (acceptable) numbering, and $\delta_a$ is the Kronecker delta function, which is $\delta_a(a) = 1$ and $\delta_a(a') = 0$ for all $a' \neq a$. Let $P^{(1)}_1$ denote the subset of $P^{(1)}$ consisting of functions that have at least one nonzero output value (note that these are precisely the functions $\psi_{(a,b)}$ such that $\varphi_b(a)$ halts). Then for any subset $\emptyset \neq S \subsetneq P^{(1)}_1$, the function $$s(a,b)=1 \text{ iff } \psi_{(a,b)} \in S$$ is not computable. We mimic the proof of Rice's Theorem; suppose $s$ were computable. Let $(a_0,b_0)$ be such that $\psi_{(a_0,b_0)} \notin S$ and let $(a_1,b_1)$ be such that $\psi_{(a_1,b_1)} \in S$. Let $D(p)$ be the total computable function which proceeds as follows:

• $D(0)=0$
• $D(p)(n)$ = if $s(p)=1$ then $\psi_{(a_0,b_0)}(n)$, otherwise $\psi_{(a_1,b_1)}(n)$

Now, if $s$ is computable, then so is $D$, and furthermore, $D$ is in $P^{(2)}_1$, so there is some index $(a_d,b_d)$ for $D$. Then consider $D((a_d,b_d))$: if $s((a_d,b_d))=1$ then $D((a_d,b_d)) = \psi_{(a_0,b_0)} \notin S$, and if $s((a_d,b_d))=0$ then $D((a_d,b_d)) = \psi_{(a_1,b_1)} \in S$, so either way $s$ gets it wrong.

(1b) The above relied on the fact that although we don't have a total computable compiler from $\varphi$ to $\psi$, we at least had a partial one which covered a nontrivial set of functions. I wouldn't be surprised if you can cook up a realizable numbering where there's essentially no such partial compiler.

(2) Since a $\psi$-Rice's Theorem fails for $\{f\}$, $\psi$ also must not satisfy the S-m-n Theorem (currying). In particular, there is some $n$ such that $\psi_n(x,y) = \varphi_x(y)$ (i.e., a universal TM). But then there is no computable program transformation $t$ such that $\psi_{t(m,x)}(y) = \psi_m(x,y)$ for all $m,x,y$, for if there were, $t(n,x)$ would enable you to decide whether $\varphi_x = f$, which is undecidable by the usual Rice's Theorem. Currying is a pretty basic feature for a programming environment to lack. I think one can prove a similar thing not just for currying, but for infinitely many program transformations, probably whenever the transformation is not finitely different from the identity map and has $f$ in its image.