Recursieve verzameling

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

Een deelverzameling van de natuurlijke getallen wordt recursief, ook berekenbaar of beslisbaar genoemd, als er een algoritme bestaat dat in eindige tijd correct kan bepalen of een getal tot de verzameling behoort. De benodigde tijd kan afhankelijk zijn van het getal.

Definitie[bewerken]

Een deelverzameling van de natuurlijke getallen wordt recursief genoemd' als er een berekenbare functie bestaat waarvoor geldt: als en als . Met andere woorden: is recursief als de Indicatorfunctie van berekenbaar is.

Voorbeelden[bewerken]

  • De lege verzameling is recursief.
  • De gehele verzameling van natuurlijke getallen is recursief.
  • Elke eindige deelverzameling van de natuurlijke getallen is recursief.