More Intensional Versions of Rice’s Theorem

Abstract

Classic results in computability theory concern extensional results: the behaviour of partial recursive functions rather than the programs computing them. We prove a generalisation of Rice’s Theorem concerning equivalence classes of programs and show how it can be used to study intensional properties such as time and space complexity. While many results that follow from our general theorems can - and have - been proved by more involved, specialised methods, our results are sufficiently simple that little work is needed to apply them.

A very preliminary version of this paper first appeared at the DICE ’16 workshop [12].

A Material Omitted from the Main Text

Proof

(Full proof of intrication from Example 3). We prove that the switching family $( \pi _{a,b} )_{(a,b) \in (\cup F) \times (\cup G)}$ is $\textsc {RE}$-F-G-intricated with $\Bumpeq _\mathtt {s}$:

If $\mathtt {p}\in \cup F$, $\mathtt {q}\in \cup G$ and $T' \in \mathcal {T}$ such that $A_{\mathtt {p},\mathtt {q}} \subseteq \pi _{\mathtt {p},\mathtt {q}} ^{-1}(T')$, there are two cases:

• If $\phi _{\mathtt {p}} = \phi _{\mathtt {q}}$, then $A_{\mathtt {s},\mathtt {p}} = B_{\mathtt {s},\mathtt {q}}$, and there is clearly no set separating $A_{\mathtt {s},\mathtt {p}}$ from $B_{\mathtt {s},\mathtt {q}}$.

• If $\phi _{\mathtt {p}} \ne \phi _{\mathtt {q}}$, there are again two cases:

  • If r does not halt on n, then $\phi _{s_{r,n}} = \phi _{\mathtt {p}} = \phi _{\mathtt {s}} \in F$, and thus $(r,n) \in A_{\mathtt {p},\mathtt {q}}$. Conversely, if $(r,n) \in A_{\mathtt {p},\mathtt {q}}$, then $\phi _{s_{r,n}} = \phi _{\mathtt {s}}$, and as $\lnot (\mathtt {q}\Bumpeq \mathtt {s})$, this implies that r does not halt on n.

  • If r halts on n, then $\phi _{s_{r,n}} \bumpeq \phi _{\mathtt {q}}$. As $\mathtt {q}\in \cup G$, we have $\lnot (\mathtt {q}\Bumpeq \mathtt {s})$, and thus $\lnot (\phi _{s_{r,n}} \Bumpeq \mathtt {s})$, whence in particular $\phi _{s_{r,n}} \ne \phi _{\mathtt {s}}$, and hence $\phi _{s_{r,n}} \Bumpeq _\mathtt {s}\mathtt {q}$. Thus, $(r,n) \in B_{\mathtt {p},\mathtt {q}}$. Conversely, if $(r,n) \in B_{\mathtt {p}, \mathtt {q}}$, $s_{r,n} \Bumpeq _\mathtt {s}\mathtt {q}$ which–as $\lnot (\mathtt {q}\Bumpeq \mathtt {p})$–implies $\phi _{s_{r,n}} \ne \phi _{\mathtt {s}}$ and hence that r halts on n.

  Thus $(r,n) \in A_{\mathtt {p},\mathtt {q}}$ iff r does not halt on n, and $(r,n) \in B_{\mathtt {p}, \mathtt {q}}$ iff r halts on n. Hence, $A_{\mathtt {p},\mathtt {q}} \cup B_{\mathtt {p},\mathtt {q}} = \mathcal {P}\times \mathcal {N}$, and $A_{\mathtt {p},\mathtt {s}}$ are $B_{\mathtt {p},\mathtt {s}}$ is co-r.e.-complete and r.e.-complete, respectively. If there were an an r.e. set C such that $A_{\mathtt {p},\mathtt {q}} \subseteq C$ and $B_{a,b} \cap C = \emptyset$, then $A_{\mathtt {p},\mathtt {q}} \cup B_{\mathtt {p},\mathtt {q}} = \mathcal {P}\times \mathcal {N}$ implies $A_{a,b} = C$, whence $A_{a,b }$ is r.e., contradicting that it is co-r.e.-complete.    $\square$