Turingmaskine

En Turingmaskine er en matematisk model for en simpel symbolmanipulerende maskine som trods sin enkle opbygning kan udføre ikke-trivielle beregninger og simulere logikken i enhver computer. Turingmaskiner blev først beskrevet af Alan Turing i 1936. De spiller en central rolle inden for datalogien i teorierne vedrørende beregnelighed og beregningers kompleksitet og generelt i matematisk logik.

En Turingmaskine kan være en specifik Turingmaskine som er konstrueret til at løse et bestemt problem, eller det kan være en universel Turingmaskine som kan læse en kodet beskrivelse af en vilkårlig Turingmaskine og dennes inputdata, og derefter udføre dens beregninger.

Uformel beskrivelse

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:

1. Et BÅND som er inddelt i celler på en række. Hver celle indeholder et symbol fra et endeligt alfabet. Alfabetet indeholder et specielt blank-symbol og et eller flere andre symboler. Celler som endnu ikke er tilskrevet noget, forudsættes at indeholde det blanke symbol.
2. Et HOVED 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.
3. En TABEL
4. Et tilstandsregister

Bemærk at enhver del af maskinen -- dens tilstands- og symbolmængde -- dens mulige skridt -- skrivning, sletning og bevægelse af hoved -- er endelig, diskret og skelnelig; det er det uendelige bånd som giver den en ubegrænset mængde lagerplads.

Formel definition

En Turingmaskine er en 7-tuple $(Q,\Sigma ,\Gamma ,\delta ,q_{0},q_{accept},q_{afvis})\,$, hvor $Q,\Sigma ,\Gamma \,$ er endelige mængder.

1. $Q\,$ er mængden af tilstande,
2. $\Sigma \,$ er inputalfabetet, uden det specielle blanke symbol $^{\sqcup }$.
3. $\Gamma \,$ er båndalfabetet, $\Sigma \subseteq \Gamma \,$ og ${\sqcup }\in \Gamma \,$,
4. $\delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}$ er transitionsfunktionen,
5. $q_{0}\in Q$ er starttilstanden,
6. $q_{accept}\in Q$ er accepttilstanden, og
7. $q_{afvis}\in Q$ er den afvisende tilstand, $q_{afvis}\neq q_{accept}$

Se også

• Flerbånds-Turingmaskine
• Nondeterministisk Turingmaskine
• Turingtest
• Enumerator
• Church-Turing-tesen
• Turing-komplet
• Halting-problemet
• Beregnelighed

• Wikimedia Commons har flere filer relateret til Turingmaskine

Spire Denne artikel om datalogi eller et datalogi-relateret emne er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den.