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

↑ Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. MIT Press. ISBN 0-262-68052-1.

References

Cutland, Nigel (1980). Computability: an introduction to recursive function theory. Cambridge University Press. ; Theorem 7-2.16.
Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. MIT Press. p. 482. ISBN 0-262-68052-1.
Odifreddi, Piergiorgio (1989). Classical Recursion Theory. North Holland.

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