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.

Definitie[bewerken | brontekst bewerken]

Een deelverzameling ${\displaystyle D}$ van de natuurlijke getallen wordt recursief genoemd, als de indicatorfunctie ${\displaystyle 1_{D}}$ van ${\displaystyle D}$ berekenbaar is.

Voorbeelden[bewerken | brontekst bewerken]

• 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.