Der er for få eller ingen kildehenvisninger i denne artikel, hvilket er et problem. Du kan hjælpe ved at angive troværdige kilder til de påstande, som fremføres i artiklen.

Beregnelighed (også kaldet komputabilitetsteori) er et emne indenfor diskret matematik, som handler om om en givet funktion kan komputeres (beregnes) af en givet maskine (ofte Turing-maskinen). Et eksempel kunne være Alan Turings bevis for halting-problemet, hvor han viste at der ikke findes en algoritme, som kan blive udregnet af en normal computer (Turing-ækvivalent), der kan finde ud af om et givet program nogensinde stopper med et givet input.

En funktion er beregnelig, hvis den kan udføres af enhver Turing-komplet maskine, altså enhver maskine, som kan simulere Turingmaskinen.

Spire Denne artikel om matematik er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at .