<p>tl;dr:</p>

<p>(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.</p>

<p>(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.</p>

<p>Elaboration:</p>

<p>(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: </p>

<ul>
<li>$D(0)=0$</li>
<li>$D(p)(n)$ = if $s(p)=1$ then $\psi_{(a_0,b_0)}(n)$, otherwise $\psi_{(a_1,b_1)}(n)$</li>
</ul>

<p>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.</p>

<p>(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.</p>

<p>(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.</p>

CC BY-SA 3.0
2017-04-20T18:48:45.127Z
2017-04-20T18:48:45.127Z
Joshua Grochow
<p>It is an easy task to devise an encoding for a computing formalism (such as  Turing Machines) that has a function with <em>fixed encoding</em>. 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 <em>realizable</em>, 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.</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Rice%27s_theorem#Formal_statement" rel="noreferrer">Wikipedia</a>, 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$.</p>

<p>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.</p>

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

CC BY-SA 3.0
2017-04-20T00:16:03.543Z
In order to avoid a Rice's Theorem for your numbering, your programming environment must also be lacking some other features which I think it would be somewhat unpleasant to live without...
Joshua Grochow
CC BY-SA 3.0
2017-04-20T00:47:31.650Z
@JoshuaGrochow I can add a bit more of detail in the original post, but basically, take a standard numbering $\phi$ on, say, TMs. Then fix for example the constant zero function's new code as 0. We use the remaining $N-\{0\}$ as follows. Fix a computable bijective mapping $M$ from $N-\{0\}$ into $\mathbb{N}^2$. Now take a code $n \in N-\{0\}$, and numbers $a,b$ where $M(n) = (a,b)$. $n$ corresponds to the function $\phi(b)$, except on input $a$, where it is $\phi(b)+1$. It should be clear that $n$ cannot correspond to the constant zero function, but all computable functions are encoded still.
hcp
CC BY-SA 3.0
2017-04-20T00:49:12.390Z
(uh, where there's $N$, please read $\mathbb{N}$, i didn't realize this at first and now i'm out of characters in the previous comment)
hcp
CC BY-SA 3.0
2017-04-20T01:07:43.370Z
Also, i apologize for not answering your comment directly. But what you ask for is also possible; $\psi$ take as input a code as i described in the previous comment, and returns the standard code of a Turing Machine that simulates the behaviour i described. Put simply, if it recieves 0, it returns the code of a constant zero function, otherwise it breaks the input into $(a,b)$ and returns the machine that would behave as the one encoded by $b$ except on input $a$ where it adds 1.
hcp
<computability>
Is there a formulation of Rice's Theorem that does not involve admissible (or Gödel) numberings?
hcp
# Is there a formulation of Rice's Theorem that does not involve admissible (or Gödel) numberings?

(Asked by: username_0 on 2017-04-19)

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](https://en.wikipedia.org/wiki/Rice%27s_theorem#Formal_statement), 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?

**Tags:** computability
> **Comments:**
> **username_1**: In order to avoid a Rice's Theorem for your numbering, your programming environment must also be lacking some other features which I think it would be somewhat unpleasant to live without...  
> **username_0**: @JoshuaGrochow I can add a bit more of detail in the original post, but basically, take a standard numbering $\phi$ on, say, TMs. Then fix for example the constant zero function's new code as 0. We use the remaining $N-\{0\}$ as follows. Fix a computable bijective mapping $M$ from $N-\{0\}$ into $\mathbb{N}^2$. Now take a code $n \in N-\{0\}$, and numbers $a,b$ where $M(n) = (a,b)$. $n$ corresponds to the function $\phi(b)$, except on input $a$, where it is $\phi(b)+1$. It should be clear that $n$ cannot correspond to the constant zero function, but all computable functions are encoded still.  
> **username_0**: (uh, where there's $N$, please read $\mathbb{N}$, i didn't realize this at first and now i'm out of characters in the previous comment)  
> **username_0**: Also, i apologize for not answering your comment directly. But what you ask for is also possible; $\psi$ take as input a code as i described in the previous comment, and returns the standard code of a Turing Machine that simulates the behaviour i described. Put simply, if it recieves 0, it returns the code of a constant zero function, otherwise it breaks the input into $(a,b)$ and returns the machine that would behave as the one encoded by $b$ except on input $a$ where it adds 1.  

---

## 1 answers

### Answer by username_1 on 2017-04-20. Score: 6

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.


---

