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):=\$ 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 \$ 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.

Notes

References

*; Theorem 7-2.16.
*
*

Theorems in the foundations of mathematics
Theorems in theory of computation

{{comp-stub