Recursieve verzameling

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.

DefinitieBewerken

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.

VoorbeeldenBewerken

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