Turingmaskin

En turingmaskin er en tenkt, formelt beskrevet maskin som utfører ordre etter en helt bestemt oppskrift eller en tabell. Maskinen er en idealisert og formell beskrivelse av en datamaskin, og hvilke beregninger eller oppgaver en datamaskin kan utføre. Maskinen er idealisert i den forstand at den har uendelig stor lagringsplass (hukommelse), og den gjør aldri feil på grunn av sine fysiske mekanismer. Det var Alan Turing som først beskrev en slik maskin i sin avhandling On Computable Numbers i 1936.

En turingmaskin består av et lese/skrive-hode som kan lese/skrive tegn fra/til ruter på en papirstrimmel. Maskinen har mange, men et endelig antall tilstander som beskriver hva som skal gjøres når et bestemt tegn leses. For hvert tegn som leses, gjøres to ting: maskinen skriver eventuelt et nytt tegn til strimmelen, og endrer tilstanden. Maskinen har en start-tilstand og en slutt-tilstand. «Resultatet» av beregningene står til slutt på strimmelen.

Alan Turing brukte en formell beskrivelse av en slik maskin for å bevise setninger innen matematikken. Siden har interessen rundt hans abstrakte maskiner (de ble først senere kalt turingmaskiner) vokst i forbindelse med fremveksten av datamaskiner, og hva datamaskiner egentlig kan utføre av beregninger. Det ser ut til at ingen maskin kan være «kraftigere» enn en turingmaskin i den forstand at ingen annen maskin kan utføre oppgaver som ikke også turingmaskinen klarer.

Formell definisjon

Det er flere måter å definere turingmaskiner på, typiske forskjeller handler om hvor mange teiper maskinen har og om teipen skal være uendelig begge veier, eller bare en vei. Det som er fint, er at disse forskjellene ikke har noe å si for hva turingmaskinen greier å beregne. Følgelig kan man velge den definisjonen av turingmaskiner som man selv finner mest passende.

Her gis en formell definisjon av en turingmaskin med én teip, og hvor teipen er uendelig begge veier. En turingmaskin $\textstyle {}M$ kan defineres som et 7-tuppel $\textstyle {}(Q,\Sigma ,\Gamma ,\delta ,q_{0},q_{accept},q_{reject})$ hvor

$\textstyle {}Q$ er en endelig, ikke-tom mengde tilstander,
$\textstyle {}\Sigma$ er input-alfabet, som ikke inneholder det blanke symbolet $\textstyle {}\mathrm {\textvisiblespace}$ ,
$\textstyle {}\Gamma$ er tape-alfabetet, som inneholder det blanke symbolet, og $\textstyle {}\Sigma \subseteq \Gamma$ ,
$\textstyle {}\delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}$ er transisjonsfunksjonen,
$\textstyle {}q_{0}\in Q$ er starttilstanden,
$\textstyle {}q_{accept}\in Q$ er den akspeterende tilstanden, og
$\textstyle {}q_{reject}\in Q$ er den avvisende tilstanden, hvor $\textstyle {}q_{accept}\not =q_{reject}$ .

Man tenker seg en turingmaskin som en endelig tilstandsmaskin som manipulerer en teip. Tilstanden til en turingmaskin kan dermed representeres ved å huske følgende: tilstanden til den endlige tilstandmaskinen, innholdet på teipen og lokasjonen til lese/skrive-hodet. Dette kan representeres som et tretuppel $\textstyle {}(s,q,t)$ , hvor maskinen står i tilstand $\textstyle {}q$ , og $\textstyle {}s$ og $\textstyle {}t$ representerer innholdet på teipen til henholds vis venstre og høyre side av lesehodet (det første elementet i $\textstyle {}t$ er hva lesehodet peker på). Merk at strengene $\textstyle {}s$ og $\textstyle {}t$ er endelige, de teip-lokasjonene som ikke blir gitt av dem er antatt å være blanke ( $\mathrm {\textvisiblespace}$ ). Et slikt tuppel kalles en konfigurasjon.

Det er nå mulig å definere hvordan er turingmaskin beregner som en relasjon $\textstyle {}k_{1}\Rightarrow k_{2}$ , hvor $\textstyle {}k_{1}$ og $\textstyle {}k_{2}$ er konfigurasjoner. Inuitivt betyr $\textstyle {}k_{1}\Rightarrow k_{2}$ at hvis en tilstandsmaskin står i tilstanden $\textstyle {}k_{1}$ , så kan den i ett steg gå til tilstanden $\textstyle {}k_{2}$ .

Formelt kan dette defineres som: Gitt $\textstyle {}a,b,c\in \Gamma$ , $\textstyle {}s,t\in \Gamma ^{*}$ og $\textstyle {}q\in Q$ , hvor $\textstyle {}q\not =q_{accept}$ og $\textstyle {}q\not =q_{reject}$ . Så er det slik at:

Hvis $\textstyle {}\delta (q,b)=(q',c,R)$ , så holder $\textstyle {}(sa,q,bt)\Rightarrow (sac,q',\lceil t\rceil )$ .
Hvis $\textstyle {}\delta (q,b)=(q',c,L)$ , så holder $\textstyle {}(sa,q,bt)\Rightarrow (\lceil s\rceil ,q',act)$ .

Formålet med funksjonen $\textstyle {}\lceil \cdot \rceil$ er å legge til blanke symboler hvis man beveger seg «utenfor» teipen. Funksjonen kan defineres som
$\lceil x\rceil =\left\{{\begin{array}{cc}x&x\not =\epsilon \\\mathrm {\textvisiblespace} &x=\epsilon \end{array}}\right.$
hvor $\textstyle {}\epsilon$ er den tomme strengen.

Det er nå mulig å definere språket til en turingmaskin. Intuitivt er det de ordene som turingmaskinen godtar. Dette kan defineres formelt som ${\mathcal {L}}(M)=\{w\in \Sigma ^{*}\mid start(w)\Rightarrow ^{*}(s,q_{accept},t)\}$ hvor $\textstyle {}start(w)=(\mathrm {\textvisiblespace} ,q_{0},\lceil w\rceil )$ , og $\textstyle {}\Rightarrow ^{*}$ er den refleksiv, transitive tillukningen av $\textstyle {}\Rightarrow$ .

Språket til en turingmaskin er kjent som turinggjenkjennelige språk. Disse språka kan i henhold til Chomskyhierarkiet gjenkjenne både de kontekstsensitive språka, de kontekstfrie språka og de regulære språka.

Kilder

Turing, A.M. (1936), «On Computable Numbers, with an Application to the Entscheidungsproblem», Proceedings of the London Mathematical Society, 2 42: 230–65, 1937 (and Turing, A.M. (1937), «On Computable Numbers, with an Application to the Entscheidungsproblem: A correction», Proceedings of the London Mathematical Society, 2 43: 544–6 ). Reprinted in many collections, e.g. in The Undecidable pp. 115–154; available on the web in many places, e.g. at Scribd.