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.

Turingmaschinn Modell Davey

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'$ 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 $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\vdash oq_{1}a\vdash oaq_{1}o\vdash oaoq_{2}o\vdash oaq_{3}oa\vdash oq_{4}aoa\vdash q_{4}oaoa\vdash aq_{0}aoa\vdash aoq_{1}oa$ $\vdash aooq_{2}a\vdash aooaq_{2}o\vdash aooq_{3}aa\vdash aoq_{3}oaa\vdash aq_{4}ooaa\vdash aaq_{0}oaa\vdash aaq_{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.

Um Spaweck

Commons: Turingmaschinnen – Biller, Videoen oder Audiodateien