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.

Question book-4.svg 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.
ArtikelstumpStub
Denne artikel er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den.