Rice–Shapiro theorem

Formal statement

Let A be a set of partial-recursive unary functions on the domain of natural numbers such that the set I x ( A ) := { n ∣ φ n ∈ A } is recursively enumerable, where φ n denotes the n -th partial-recursive function in a Gödel numbering.

Then for any unary partial-recursive function ψ , we have:

In the given statement, a finite function is a function with a finite domain x 1 , x 2 , . . . , x m and θ ⊆ ψ means that for every x ∈ { x 1 , x 2 , . . . , x m } it holds that ψ ( x ) is defined and equal to θ ( x ) .

Perspective from Effective Topology

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

I x ( A ) is recursively enumerable iff A is a recursively enumerable union of frusta.