Rice–Shapiro theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

The statement can be expressed informally as follows: given that a computable function (viewed as a black-box) is an infinite object[clarification needed], 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.[citation needed]

Formal statement[edit]

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[edit]

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

References[edit]

  • 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.