Conjunt recursivamente enumerable

En teoria de la computabilidad, un conjunt S de número natural es denomina computablemente enumerable (ce), recursivamente enumerable (re), semidecidible, parcialment decidible, enumerable, demostrador o Turing-reconeixible si:

Existix un algoritme que es deté exactament per als números d'entrada de S.

O equivalentemente,

Hi ha un algoritme que enumera els membres de S. És dir, la seua eixida és una llista dels elements de S: s₁, s₂, s₃, ... . Si S és infinit, este algoritme s'eixecuta indefinidament.

La primera condició sugerix per qué a voltes s'usa el terme semidecidible: Si un número pertany al conjunt, un ho pot decidir eixecutant l'algoritme, pero si el número no està en el conjunt, l'algoritme no torna informació. Un conjunt que és "completament decidible" és un conjunt computable. La segona condició sugerix per qué s'usa computablemente enumerable. Les abreviatures c.i. i r.i. s'usen a sovint.

En la teoria de la complexitat computacional, la classe de complexitat que conté tots els conjunts computablemente enumerables és RE. En la teoria de la recursión, el retícul de conjunts c.i. baix inclusió es denota $ℰ$ .

Definició formal

Un conjunt S d'número natural es diu computablemente enumerable si hi ha una funció computable parcial que el seu domini és exactament S, lo que significa que la funció es definix si i solament si la seua entrada és un membre de S.

Formulació equivalents

Les següents propietats d'un conjunt de naturals S són equivalents:

Semidecidibilidad :

El conjunt S és computablemente enumerable. És dir, S és el domini d'una funció computable parcial.
El conjunt S és $Σ_{1}^{0}$ (referint-se a la jerarquia aritmètica).^[1]
Existix una funció computable parcial f tal que: $f (x) = {\begin{matrix} 1 & si x \in S \\ indefinida/no termina & si x \notin S \end{matrix}$

Enumerabilidad :

El conjunt S és el ranc d'una funció computable parcial.
El conjunt S és el ranc d'una funció computable total, o buit. Si S és infinit, la funció podria ser inyectiva.
El conjunt S és l'image (ranc) d'una funció recursiva primitiva o buida. Si S és infinit pot ser necessària la repetició de valors.

Diofántico :

Hi ha un polinomi p en coeficients sancers i variables x, a, b, c, d, i, f, g, h, i oscilant entre els número natural tal que $x \in S \Leftrightarrow \exists a, b, c, d, e, f, g, h, i (p (x, a, b, c, d, e, f, g, h, i) = 0) .$
Existix un polinomi de sancers a sancers tal que el conjunt S conté exactament els números no negatius en la seua image.

L'equivalència de semidecidibilidad i enumerabilidad es pot obtindre per mig de la tècnica de dovetailing.

Yuri Matiyasevich va trobar les caracterisació diofánticas d'un conjunt computablemente enumerable com a part de la resposta negativa al Dècim problema de Hilbert. Els conjunts diofánticos són anteriors a la teoria de la recursividad i, per lo tant, varen ser la primera caracterisació d'estos conjunts (la seua equivalència es demostraria més de tres décades després de l'introducció de conjunts c.i.).

Vore també

Referències

↑ Downey, Rodney G.; Hirschfeldt, {{{nom2}}} (2010-10-29). Algorithmic Randomness and Complexity (en en), Springer Science & Business Mija, p. 23. ISBN 978-0-387-68441-3.

Bibliografia

Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. Plantilla:Isbn.
Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. Plantilla:Isbn.
Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181.

Referències

Este artícul conté una traducció derivada de «Conjunto recursivamente enumerable» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Downey, Rodney G.; Hirschfeldt, {{{nom2}}} (2010-10-29). Algorithmic Randomness and Complexity (en en), Springer Science & Business Mija, p. 23. ISBN 978-0-387-68441-3.

[1]