Turingmaschinn

Eng **Turingmaschinn** ass een einfache mathematesche Modell vun engem Rechenautomat, dee 1936 vum brittesche Mathematiker, Kryptoanalytiker a Computerconstructeur Alan Turing definéiert gouf. D'Church-Turing Thees seet, dat all déi am intuitive Sënn berechebar Funktioune mat enger Turingmaschinn geléist kënne ginn.

## Definitioun
### Informell Beschreiwung

D'Turingmaschinn besteet aus dräi Deeler:
* engem no béide Säiten onendlech laangem Band, wat a gläich grouss Zellen agedeelt ass. All Zell ka just een Zeechen ophuelen.
* enger Steiereenheet oder Kontrolleenheet mat endlech villen Zoustänn.
* engem beweegleche Lies-/Schreifkapp.

#### Aarbechtsweis
Am Ufank ass d'Maschinn am Startzoustand an de Kapp steet op deem éischten Zeeche vun der Eingabe. D'Maschinn liest Zeechen a ënner dem Kapp a féiert an Ofhängegkeet vun a an dem Zoustand q eng Aktioun aus. Dobäi gëtt een Zeeche b op déi aktuell Positioun vum Kapp op d'Band geschriwwen. De Kapp beweegt sech **eng** Positioun no lénks (L), riets (R) oder bleift stoen (N) an d'Kontroll geet an een neien Zoustand q' iwwer. Elo gëtt nees een Zeeche gelies a sou weider. D'Berechnung ass fäerdeg, wann d'Kontroll an een Endzoustand gaangen ass.

### Formal Definitioun
Eng Turingmaschinn ass en 7-Tupel

M=(Q,\Sigma,\Gamma,\delta,q_0,\Box,E), woubäi

* Q ass den endlechen Ensembel vun Zoustänn,
* \Sigma ass d'Eingabealphbet,
* \Gamma ass d'Bandalphabet (\Gamma\supset\Sigma),
* \delta:Q\times\Gamma\rightarrow Q\times\Gamma\times\{L,R,N\} ass d'Iwwergangsfunktioun,
* q_0\in Q ass de Startzoustand,
* \Box\in\Gamma\setminus\Sigma steet fir e Blank
* E\subseteq Q ass den endlechen Ensembel vun Endzoustänn

Informell bedeit:

\delta(q,a)=(q',b,m)

Wann d'Turingmaschinn M am Zoustand q an dat aktuellt Zeechen a ass, da geet M an den Zoustand q' iwwer, iwwerschreift a duerch b a mécht d'Kappbeweegung m\in\{L,R,N\}.

## Beispill
Déi follgend Turingmaschinn M erwaart eng Rei vun aen als Eingabe a verduebelt dës da mat engem Blank (representéiert als o) an der Mëtt:

M=(\{q_0,q_1,q_2,q_3,q_4,q_e\},\{a\},\{a,o\},\delta,q_0,o,\{q_e\})

\delta(q_0,a)=(q_1,o,R)
\delta(q_0,o)=(q_e,o,N)

\delta(q_1,a)=(q_1,a,R)
\delta(q_1,o)=(q_2,o,R)

\delta(q_2,o)=(q_3,a,L)
\delta(q_2,a)=(q_2,a,R)

\delta(q_3,a)=(q_3,a,L)
\delta(q_3,o)=(q_4,o,L)

\delta(q_4,a)=(q_4,a,L)
\delta(q_4,o)=(q_0,a,R)

Wann d'Maschinn M zum Beispill mat der Eingabe aa gestart gëtt, da stoppt se mat aao aa um Band. Si mécht follgend Schrëtt:

q_0aa \vdash oq_1a \vdash oaq_1o \vdash oaoq_2o \vdash oaq_3oa \vdash oq_4aoa \vdash q_4oaoa \vdash aq_0aoa \vdash aoq_1oa
\vdash aooq_2a \vdash aooaq_2o \vdash aooq_3aa \vdash aoq_3oaa \vdash aq_4ooaa \vdash aaq_0oaa \vdash aaq_eoaa

## Variante vun Turingmaschinnen
Eng k-Band Turingmaschinn besteet aus k Bänner mat all Kéier engem eegene Lies-Schreifkapp.
Dës Käpp kënne sech onofhängeg vunenee beweegen. Wichteg ass, dat dës k-Band Turingmaschinnen awer net méi mächteg sinn: zou all k-Band Maschinn existéiert eng equivalent 1-Band Turingmaschinn.

## Literatur
* Uwe Schöning: *Theoretische Informatik - kurzgefasst*. Spektrum Akademischer Verlag, 2001.
* Renate Winter: *Theoretische Informatik*. Oldenbourg Verlag, 2002.
* Rolf Herken (Erausg.): *The Universal Turing Machine - A Half-Century Survey*, Hamburg, Verlag Kammerer/Unverzagt, 1987. D'Buch ass eng Sammlung vun 30 wëssenschaftrleche Originalaufsätz fir de 50. Joresdag vun der Erfindung vum *abstakten Universalcomputer* duerch den Turing.

## Um Spaweck