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] Conteúdo 1 Declaração formal 2 Perspective from effective topology 3 Notas 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(UMA):={nmid varphi _{n}em um}} is recursively enumerable, Onde {estilo de exibição varphi _{n}} denotes the {estilo de exibição m} -th partial-recursive function in a Gödel numbering.

Then for any unary partial-recursive function {estilo de exibição psi } , temos: {displaystyle psi in ALeftrightarrow exists } a finite function {displaystyle theta subseteq psi } de tal modo que {displaystyle theta in A.} In the given statement, a finite function is a function with a finite domain {estilo de exibição x_{1},x_{2},...,x_{m}} e {displaystyle theta subseteq psi } means that for every {estilo de exibição xin {x_{1},x_{2},...,x_{m}}} it holds that {estilo de exibição psi (x)} is defined and equal to {estilo de exibição teta (x)} .

Perspective from effective topology For any finite unary function {estilo de exibição teta } on integers, deixar {estilo de exibição C(teta )} denote the 'frustum' of all partial-recursive functions that are defined, and agree with {estilo de exibição teta } , sobre {estilo de exibição teta } 's domain.

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

Notes ^ Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. Imprensa do MIT. 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. Imprensa do MIT. p. 482. ISBN 0-262-68052-1. Odifreddi, Piergiorgio (1989). Teoria da Recursão Clássica. North Holland.

This computing article is a stub. Você pode ajudar a Wikipédia expandindo-a.

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