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


This article is issued from Wikipedia - version of the Monday, April 18, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.