Turingmaschinn

D'Turingmaschinn ass een einfacht mathematescht Modell vun engem Rechenautomat, dat 1936 vum britesche Mathematiker, Kryptoanalytiker a Computerkonstrukteur Alan Turing definéiert gouf. Church-Turing Thes beseet, dat all déi am intuitive Sënn berechebar Funktioune mat enger Turingmaschinn léisbar sinn.

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 beweglechem Lies-/Schreifkapp.

Aarbechtsweis

Am Ufank befënnt sech 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 Zeechen $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 an esou weider. D'Berechnung ass fäerdeg, wann d'Kontroll an een Endzoustand gaang ass.

Formal Definitioun

Eng Turingmaschinn ass en 7-Tupel

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

• $Q$ ass den endlechen Ensemble 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 Ensemble vun Endzoustänn

Informell bedeit:

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

Befënnt sech Turingmaschinn $M$ am Zoustand $q$ an dat aktuellt Zeechen ass $a$, da geet $M$ an den Zoustand $q'$ iwwer, iwwerschreift $a$ duerch $b$ a féiert Kappbewegung $m\in\{L,R,N\}$ duerch.

Beispill

Déi folgend 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 $aao aa$ um Band. Si mécht folgend 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éiers 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.

Commons: Turing machine – Biller, Videoen oder Audiodateien