Rice–Shapiro theorem

In computability theory, the Rice–Shapiro theorem is a generalization of Rice's theorem, and is named after Henry Gordon Rice and Norman Shapiro.

Formal statement

Let A be a set of partial-recursive unary functions on the domain of natural numbers such that the set $Ix(A):=\{n\mid \varphi _{n}\in A\}$ is recursively enumerable, where $\varphi _{n}$ denotes the $n$-th partial-recursive function in a Gödel numbering.

Then for any unary partial-recursive function $\psi$, we have:

$\psi \in A\Leftrightarrow \exists$ a finite function $\theta \subseteq \psi$ such that $\theta \in A.$

In the given statement, a finite function is a function with a finite domain $x_{1},x_{2},...,x_{m}$ and $\theta \subseteq \psi$ means that for every $x\in \{x_{1},x_{2},...,x_{m}\}$ it holds that $\psi (x)$ is defined and equal to $\theta (x)$.

Perspective from effective topology

For any finite unary function $\theta$ on integers, let $C(\theta )$ denote the 'frustum' of all partial-recursive functions that are defined, and agree with $\theta$, on $\theta$'s domain.

Equip the set of all partial-recursive functions with the topology generated by these frusta as base. Note that for every frustum $C$, $Ix(C)$ is recursively enumerable. More generally it holds for every set $A$ of partial-recursive functions:

$Ix(A)$ is recursively enumerable iff $A$ is a recursively enumerable union of frusta.

References

• Cutland, Nigel (1980). Computability: an introduction to recursive function theory. Cambridge University Press.; Theorem 7-2.16.
• Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. MIT Press. p. 482. ISBN 0-262-68052-1.
• Odifreddi, Piergiorgio (1989). Classical Recursion Theory. North Holland.