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] Contenu 1 Déclaration formelle 2 Perspective from effective topology 3 Remarques 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(UN):={nmid varphi _{n}dans un}} is recursively enumerable, où {style d'affichage varphi _{n}} denotes the {displaystyle n} -th partial-recursive function in a Gödel numbering.

Then for any unary partial-recursive function {style d'affichage psi } , Nous avons: {displaystyle psi in ALeftrightarrow exists } a finite function {displaystyle theta subseteq psi } tel que {displaystyle theta in A.} In the given statement, a finite function is a function with a finite domain {style d'affichage x_{1},X_{2},...,X_{m}} et {displaystyle theta subseteq psi } means that for every {style d'affichage xin {X_{1},X_{2},...,X_{m}}} it holds that {style d'affichage psi (X)} is defined and equal to {thêta de style d'affichage (X)} .

Perspective from effective topology For any finite unary function {thêta de style d'affichage } on integers, laisser {displaystyle C(thêta )} denote the 'frustum' of all partial-recursive functions that are defined, and agree with {thêta de style d'affichage } , sur {thêta de style d'affichage } '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 {style d'affichage A} of partial-recursive functions: {displaystyle Ix(UN)} is recursively enumerable iff {style d'affichage A} is a recursively enumerable union of frusta.

Notes ^ Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. Presse du MIT. ISBN 0-262-68052-1. References Cutland, Nigel (1980). Computability: an introduction to recursive function theory. Cambridge University Press.; Théorème 7-2.16. Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. Presse du MIT. p. 482. ISBN 0-262-68052-1. Odifreddi, Piergiorgio (1989). Théorie de la récursivité classique. North Holland.

This computing article is a stub. Vous pouvez aider Wikipédia en l'agrandissant.

Catégories: Theorems in the foundations of mathematicsTheorems in theory of computationComputing stubs