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

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