6
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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... $\endgroup$ – Joshua Grochow Apr 20 '17 at 0:16
  • 2
    $\begingroup$ @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. $\endgroup$ – hcp Apr 20 '17 at 0:47
  • $\begingroup$ (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) $\endgroup$ – hcp Apr 20 '17 at 0:49
  • $\begingroup$ 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. $\endgroup$ – hcp Apr 20 '17 at 1:07
6
$\begingroup$

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.

$\endgroup$

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.