Conjunt recursivo

En la teoria de la computabilidad, un conjunt de número natural es diu computable, recursivo o decidible si hi ha un algoritme que decidix correctament si un número pertany o no al conjunt en temps finito.

Un conjunt que no és computable es diu no computable o indecidible.

Una classe més general de conjunts que els computables són els computablemente enumerables (c.i.). Per a estos conjunts, solament es requerix que existixca un algoritme que decidixca correctament quan un número està en el conjunt; l'algoritme pot no donar una resposta (pero no la resposta incorrecta) per als números que no estan en el conjunt.

Des del punt de vista dels problemes de decisió, un conjunt recursivo és un per al qual el problema de pertinença és decidible.

Definició formal

Un conjunt $S$ de naturals es diu computable si existix una funció total computable $f$ tal que $f(x)=1$ si $x\in S$ i $f(x)=0$ si $x\notin S$ . En atres paraules, el conjunt $S$ és computable si i solament si el seu funció indicatriz lo és.

Eixemples i contraeixemples

Eixemples:

• Tot subconjunt finito o cofinito dels número natural és computable. Açò inclou estos casos especials:
  • El conjunt buit és computable.
  • El conjunt dels número natural és computable.
  • I conjunt d'número natural menors que un número natural donat és computable.
• Els número primo són computables.
• Un llenguage recursivo és un subconjunt computable d'un llenguage formal .

Contraeixemples:

• El conjunt de màquines de Turing que es detenen no és computable.
• La classe d'isomorfisme de dos complexos simpliciales finitos no és computable.
• El conjunt de campeons busy beaver no és computable.
• El dècim problema de Hilbert no és computable.

Vore també

• Llenguage recursivamente enumerable
• Llenguage recursivo
• Recursividad

Referències

• Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. Plantilla:Isbn; Plantilla:Isbn
• Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. Plantilla:Isbn; Plantilla:Isbn
• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. Plantilla:Isbn