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

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

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