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]

Informal statement

The statement can be expressed informally as follows: given that a computable function (viewed as a black-box) is an infinite object, and given that we cannot hope to develop a general algorithm for studying a property of the function on infinite input-output pairs, there is in general no truly better way than to apply the function on some inputs and hope to get their outputs.

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