Begrensetrekursiv

Begrensetrekursiv, ofte kalt begrenset rekursiv i norske tekster, er en klass av beregnbare funksjoner som kan defineres fra et sett grunnfunksjoner ved hjelp av sammensetning og primitiv rekursjon. Funksjonene i denne klassen er totale, og rekursjonen stopper alltid etter et endelig antall steg for alle inn-data. Begrepet brukes ofte i teorier om beregnbarhet og matematisk logikk for å beskrive funksjoner som kan beregnes uten ubegrenset søk.

De grunnleggende funksjonene består vanligvis av nullfunksjonen, etterfølgerfunksjonen og projeksjonsfunksjonene. Klassen er lukket under sammensetning og under primitiv rekursjon: hvis F og G er begrenset rekursive, så er også funksjonen definert ved sammensetting av F og G, samt funksjoner som opprettes gjennom primitiv rekursjon, begrenset rekursiv.

Eksempler er addisjon, multiplikasjon og eksponentiering, alle konstruert ved primitiv rekursjon fra basisfunksjonene. Fordelen med begrenset rekursiv definisjon er at den gir garantier om terminering og at beregningene skjer i et forutbestemt, uavhengig begrenset antall trinn.

Begrenset rekursive funksjoner er en underklasse av alle totale beregnbare funksjoner. Ikke alle totale beregnbare funksjoner er primitive rekursive; Ackermann-funksjonen er et klassisk eksempel på en total beregnbar funksjon som ikke er primitive rekursiv, noe som illustrerer forskjellen.

I norsk litteratur brukes termen ofte som synomym for primitive rekursive funksjoner, særlig i introductory-tekster om beregnbarhet og logikk. Bruksområder inkluderer teoretisk datalære, bevis for terminering og fastsettelse av tidsmessige grenser i algoritmer.