Beregnelighed: Forskelle mellem versioner
Content deleted Content added
m Datomaerker kilde mangler-skabeloner |
nutids-R |
||
Linje 1:
'''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-maskine|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
{{kilder|dato=marts 2020}}
{{Stub}}
| |||