Enturingmaskine er en matematisk model for en simpel symbolmanipulerende maskine som trods sin enkle opbygning kan udføre ikke-trivielle beregninger og simulere logikken i enhvercomputer. Turingmaskiner blev først beskrevet afAlan Turing i1936. De spiller en central rolle inden fordatalogien i teorierne vedrørendeberegnelighed ogberegningers kompleksitet og generelt i matematisk logik.
En Turingmaskine kan være enspecifik Turingmaskine som er konstrueret til at løse et bestemt problem, eller det kan være enuniversel Turingmaskine som kan læse en kodet beskrivelse af en vilkårlig Turingmaskine og dennes inputdata, og derefter udføre dens beregninger.
Turingmaskinens koncept er baseret på ideen om, at en person udfører en veldefineret procedure, ved at ændre på indholdet af et uendeligt bånd, der er inddelt i kvadrater, som hver kan indeholde ét ud af en endelig mængde symboler. Personen skal huske én ud af en endelig mængde af tilstande, og proceduren er formuleret som meget basale skridt på formen: "Hvis din tilstand er 42 og symbolet du ser er et '0', så udskift dette med et '1', ryk et symbol til højre på båndet, og som din nye tilstand; gå i tilstand 17."
Mere præcist består en Turingmaskine af:
EtBÅND som er inddelt i celler på en række. Hver celle indeholder et symbol fra et endeligt alfabet. Alfabetet indeholder et specieltblank-symbol og et eller flere andre symboler. Celler som endnu ikke er tilskrevet noget, forudsættes at indeholde det blanke symbol.
EtHOVED som kan læse og skrive symboler på båndet og rykke sig til højre og venstre på båndet, en celle af gangen.
EnTABEL
Ettilstandsregister
Bemærk at enhver del af maskinen -- dens tilstands- og symbolmængde -- dens mulige skridt -- skrivning, sletning og bevægelse af hoved -- erendelig,diskret ogskelnelig; det er det uendelige bånd som giver den en ubegrænset mængde lagerplads.
