Rice–Shapiro theorem

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] Contents 1 Formal statement 2 Perspective from effective topology 3 Notes 4 References Formal statement Let A be a set of partial-recursive unary functions on the domain of natural numbers such that the set {displaystyle Ix(A):={nmid varphi _{n}in A}} is recursively enumerable, where {displaystyle varphi _{n}} denotes the {displaystyle n} -th partial-recursive function in a Gödel numbering.

Then for any unary partial-recursive function {displaystyle psi } , we have: {displaystyle psi in ALeftrightarrow exists } a finite function {displaystyle theta subseteq psi } such that {displaystyle theta in A.} In the given statement, a finite function is a function with a finite domain {displaystyle x_{1},x_{2},...,x_{m}} and {displaystyle theta subseteq psi } means that for every {displaystyle xin {x_{1},x_{2},...,x_{m}}} it holds that {displaystyle psi (x)} is defined and equal to {displaystyle theta (x)} .

Perspective from effective topology For any finite unary function {displaystyle theta } on integers, let {displaystyle C(theta )} denote the 'frustum' of all partial-recursive functions that are defined, and agree with {displaystyle theta } , on {displaystyle theta } 's domain.

Equip the set of all partial-recursive functions with the topology generated by these frusta as base. Note that for every frustum {displaystyle C} , {displaystyle Ix(C)} is recursively enumerable. More generally it holds for every set {displaystyle A} of partial-recursive functions: {displaystyle Ix(A)} is recursively enumerable iff {displaystyle A} is a recursively enumerable union of frusta.

Notes ^ Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. MIT Press. ISBN 0-262-68052-1. References 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.

Categories: Theorems in the foundations of mathematicsTheorems in theory of computationComputing stubs