Redigerer Turingmaskin

[[Fil:Turing Machine.png|thumb|En turingmaskin er en formelt beskrevet, universell datamaskin]]
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 ([[Minne|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 [[matematikk]]en. 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 <math>\textstyle{}M</math> kan defineres som et 7-tuppel <math>\textstyle{}(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})</math> hvor
* <math>\textstyle{}Q</math> er en endelig, ikke-tom mengde tilstander,
* <math>\textstyle{}\Sigma</math> er input-alfabet, som ikke inneholder det blanke symbolet <math>\textstyle{}\textvisiblespace</math>,
* <math>\textstyle{}\Gamma</math> er tape-alfabetet, som inneholder det blanke symbolet, og <math>\textstyle{}\Sigma \subseteq \Gamma</math>,
* <math>\textstyle{}\delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}</math> er transisjonsfunksjonen,
* <math>\textstyle{}q_0 \in Q</math> er starttilstanden,
* <math>\textstyle{}q_{accept} \in Q</math> er den akspeterende tilstanden, og
* <math>\textstyle{}q_{reject} \in Q</math> er den avvisende tilstanden, hvor <math>\textstyle{}q_{accept} \not= q_{reject}</math>.

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 <math>\textstyle{}(s, q, t)</math>, hvor maskinen står i tilstand <math>\textstyle{}q</math>, og <math>\textstyle{}s</math> og <math>\textstyle{}t</math> representerer innholdet på teipen til henholds vis venstre og høyre side av lesehodet (det første elementet i <math>\textstyle{}t</math> er hva lesehodet peker på). Merk at strengene <math>\textstyle{}s</math> og <math>\textstyle{}t</math> er endelige, de teip-lokasjonene som ikke blir gitt av dem er antatt å være blanke (<math>\textvisiblespace</math>). Et slikt [[tuppel]] kalles en ''konfigurasjon''.

Det er nå mulig å definere hvordan er turingmaskin beregner som en relasjon <math>\textstyle{} k_1 \Rightarrow k_2</math>, hvor <math>\textstyle{}k_1</math> og <math>\textstyle{}k_2</math> er konfigurasjoner.
Inuitivt betyr <math>\textstyle{}k_1 \Rightarrow k_2</math> at hvis en tilstandsmaskin står i tilstanden <math>\textstyle{}k_1</math>, så kan den i ett steg gå til tilstanden <math>\textstyle{}k_2</math>.

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

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

Formålet med funksjonen <math>\textstyle{}\lceil \cdot \rceil</math> er å legge til blanke symboler hvis man beveger seg «utenfor» teipen. Funksjonen kan defineres som <br />
<math>\lceil x \rceil = \left\{\begin{array}{cc} x & x \not= \epsilon \\ \textvisiblespace & x = \epsilon \end{array} \right.</math> <br />
hvor <math>\textstyle{}\epsilon</math> 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
<math> \mathcal{L}(M) = \{ w \in \Sigma^{*} \mid start(w) \Rightarrow^{*} (s, q_{accept}, t) \} </math> 
hvor <math>\textstyle{} start(w) = (\textvisiblespace, q_0, \lceil w \rceil)</math>, og <math>\textstyle{} \Rightarrow^{*}</math> er den [[Refleksiv relasjon|refleksiv]], [[Transitiv relasjon|transitive]] [[tillukning (matematikk)|tillukningen]] av <math>\textstyle{} \Rightarrow</math>.

Språket til en turingmaskin er kjent som [[Rekursivt nummererbare språk|turinggjenkjennelige språk]]. Disse språka kan i henhold til [[Chomskyhierarkiet]] gjenkjenne både de [[kontekstsensitive språk]]a, de [[Kontekstfritt språk|kontekstfrie språka]] og de [[Regulært språk|regulære språka]].

== Kilder ==
*  {{ Citation | last= Turing | first= A.M. | publication-date = 1937 | date = 1936 | title = On Computable Numbers, with an Application to the Entscheidungsproblem | periodical = Proceedings of the London Mathematical Society | series = 2 | volume = 42 | pages = 230–65 }} (and {{Citation | last = Turing | first = A.M. | publication-date = 1937 | title = On Computable Numbers, with an Application to the Entscheidungsproblem: A correction | periodical = Proceedings of the London Mathematical Society | series = 2 | volume = 43 | pages = 544–6 }}).  Reprinted in many collections, e.g. in ''The Undecidable'' pp.&nbsp;115–154; available on the web in many places, e.g. [http://www.scribd.com/doc/2937039/Alan-M-Turing-On-Computable-Numbers at Scribd].

{{Formelle språk og grammatikker}}
{{Autoritetsdata}}

[[Kategori:Formelle språk]]
[[Kategori:Informatikk]]