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 is recursively enumerable, where denotes the -th partial-recursive function in a Gödel numbering.

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

a finite function such that

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 .

In general, one can obtain the following statement: The set is recursively enumerable iff the following two conditions hold:

(a) is recursively enumerable;

(b) iff a finite function such that extends where is the canonical index of .

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 4/18/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.