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 $\{ 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_n$ and $\theta \subseteq \psi$ means that for every $x \in \{x_1,x_2,...,x_n\}$ it holds that $\psi(x)$ is defined and equal to $\theta(x)$.

In general, one can obtain the following statement: The set $\{n: \varphi_n \in A\}$ is recursively enumerable iff the following two conditions hold:

(a) $\{\theta: \theta = \varphi_n \forall n \in A\}$ is recursively enumerable;

(b) $n \in A$ iff $\exists$ a finite function $\theta$ such that $\varphi_n$ extends $\theta \wedge c(\theta) \in A$ where $c(\theta)$ is the canonical index of $\theta$.

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.