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 is recursively enumerable, where denotes the -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 and means that for every it holds that is defined and equal to.

Perspective from effective topology

For any finite unary function on integers,
let 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, is
recursively enumerable. More generally it holds for every set
of partial-recursive functions:
is recursively enumerable iff
is a recursively enumerable union of frusta.