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 Stewart Shapiro cite book | title=Theory of Recursive Functions and Effective Computability | author=Rogers Jr., Hartley | publisher=MIT Press|isbn=0-262-68052-1 | year=1987] .

Informal statement

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.

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\; existsmbox\{\; a\; finite\; function\; \}\; heta\; subseteq\; fmbox\{\; such\; that\; \}\; heta\; in\; A.$

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

Notes

References

*cite book | title=Computability: an introduction to recursive function theory| author=Cutland, Nigel | publisher=Cambridge University Press | year=1980 ; Theorem 7-2.16.
* cite book | title=Theory of Recursive Functions and Effective Computability | author=Rogers Jr., Hartley | publisher=MIT Press|isbn=0-262-68052-1 | pages=482 | year=1987