Redigerer Turingmaskin (avsnitt)

== 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]].