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] Contenuti 1 Dichiarazione formale 2 Perspective from effective topology 3 Appunti 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}in un}} is recursively enumerable, dove {displaystyle varphi _{n}} denotes the {stile di visualizzazione n} -th partial-recursive function in a Gödel numbering.

Then for any unary partial-recursive function {stile di visualizzazione psi } , noi abbiamo: {displaystyle psi in ALeftrightarrow exists } a finite function {displaystyle theta subseteq psi } tale che {displaystyle theta in A.} In the given statement, a finite function is a function with a finite domain {stile di visualizzazione x_{1},X_{2},...,X_{m}} e {displaystyle theta subseteq psi } means that for every {stile di visualizzazione xin {X_{1},X_{2},...,X_{m}}} it holds that {stile di visualizzazione psi (X)} is defined and equal to {stile di visualizzazione theta (X)} .

Perspective from effective topology For any finite unary function {stile di visualizzazione theta } on integers, permettere {stile di visualizzazione C(teta )} denote the 'frustum' of all partial-recursive functions that are defined, and agree with {stile di visualizzazione theta } , Su {stile di visualizzazione 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 {stile di visualizzazione C} , {displaystyle Ix(C)} is recursively enumerable. More generally it holds for every set {stile di visualizzazione A} of partial-recursive functions: {displaystyle Ix(UN)} is recursively enumerable iff {stile di visualizzazione A} is a recursively enumerable union of frusta.

Notes ^ Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. MIT stampa. ISBN 0-262-68052-1. References Cutland, Nigel (1980). Computability: an introduction to recursive function theory. Cambridge University Press.; Teorema 7-2.16. Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. MIT stampa. p. 482. ISBN 0-262-68052-1. Odifreddi, Piergiorgio (1989). Teoria della ricorsione classica. North Holland.

This computing article is a stub. Puoi aiutare Wikipedia espandendolo.

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

Se vuoi conoscere altri articoli simili a Rice–Shapiro theorem puoi visitare la categoria Computing stubs.

lascia un commento

L'indirizzo email non verrà pubblicato.

Vai su

Utilizziamo cookie propri e di terze parti per migliorare l'esperienza dell'utente Maggiori informazioni