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.[1]

Formal statement

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

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

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

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

Perspective from effective topology

For any finite unary function ${\displaystyle \theta }$ on integers, let ${\displaystyle C(\theta )}$ denote the 'frustum' of all partial-recursive functions that are defined, and agree with ${\displaystyle \theta }$, on ${\displaystyle \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 ${\displaystyle C}$, ${\displaystyle Ix(C)}$ is recursively enumerable. More generally it holds for every set ${\displaystyle A}$ of partial-recursive functions:

${\displaystyle Ix(A)}$ is recursively enumerable iff ${\displaystyle A}$ is a recursively enumerable union of frusta.

Notes

1. Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. MIT Press. ISBN 0-262-68052-1.

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.