Turingmaschinn

Turingmaschinn Modell Davey

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

Eng 1-Band Turingmaschinn

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^{\prime }$ 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,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,◻,E)$, woubäi

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

Informell bedeit:

$\delta (q,a)=(q^{\prime },b,m)$

Wann d'Turingmaschinn $M$ am Zoustand $q$ an dat aktuellt Zeechen $a$ ass, da geet $M$ an den Zoustand $q^{\prime }$ 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 $a$en 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 $aaoaa$ um Band. Si mécht follgend Schrëtt:

$q_{0}aa⊢o{q}_{1}a⊢oa{q}_{1}o⊢oao{q}_{2}o⊢oa{q}_{3}oa⊢o{q}_{4}aoa⊢q_{4}oaoa⊢a{q}_{0}aoa⊢ao{q}_{1}oa$ $⊢aoo{q}_{2}a⊢aooa{q}_{2}o⊢aoo{q}_{3}aa⊢ao{q}_{3}oaa⊢a{q}_{4}ooaa⊢aa{q}_{0}oaa⊢aa{q}_{e}oaa$

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.