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.
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 .
- 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 computing article is a stub. You can help Wikipedia by expanding it.|