Rice-Shapiro theorem

From Wikipedia, the free encyclopedia

In computer science, and in particular in the theory of computable functions, the Rice-Shapiro theorem is in some sense a generalization of Rice's theorem, and is named after Henry Gordon Rice and Stewart Shapiro^{[citation needed]}.

The statement can be expressed informally as follows: given that a computable function (viewed as a black-box) is an infinite object, and we cannot hope to develop a general algorithm studying a property of 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.

[edit] Formal statement

Let $A$ be a set of computable 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 computable function in a Gödel numbering.

Then for any unary computable function $f$ , we have:

$f \in A \Leftrightarrow \exists\mbox{ a finite function }\theta \subseteq f\mbox{ such that }\theta \in A.$

In the given statement, $\theta \subseteq f$ means that $θ$ is an approximation of $f$ , and finite function refers to a function defined on a finite set of input values.