En beregningsbar funksjon (eller rekursiv funksjon ) er en semi-beregningsbar funksjon (eller rekursiv delvis funksjon ) som også er total , det vil si definert over hele sitt domene. Dette er funksjonene som er beregnet av en "avsluttende" Turing-maskin .
En kalkulerbar funksjon er ikke nødvendigvis "fysisk kalkulerbar", for eksempel hvis dens gjennomføringstid overstiger flere milliarder år.
De enkleste eksemplene på beregningsfunksjoner er konstante funksjoner . En konsekvens av prinsippet om den utelukkede tredje er da at den konstante funksjonen som til et heltall forbinder 1 hvis antagelsen om Goldbach er sann og 0 hvis den er falsk, kan beregnes, selv om vi ikke i dag vet om antagelsen er sant. Dette viser hvordan anvendelsen av dette prinsippet ødelegger enhver intuitiv forestilling om beregbarhet.