Recursieve verzameling

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

DefinitieBewerken

Een deelverzameling   van de natuurlijke getallen wordt recursief genoemd, als de indicatorfunctie   van   berekenbaar is.

VoorbeeldenBewerken

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