Beregnelighed

Fra Wikipedia, den frie encyklopædi
Spring til navigation Spring til søgning

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 simulerer Turingmaskinen.