Turingmaschinn

D'Church-Turing Thees seet, dat all déi am intuitive Sënn berechebar Funktioune mat enger Turingmaschinn geléist kënne ginn.

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 ${\displaystyle a}$  ënner dem Kapp a féiert an Ofhängegkeet vun ${\displaystyle a}$  an dem Zoustand ${\displaystyle q}$  eng Aktioun aus. Dobäi gëtt een Zeeche ${\displaystyle 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 ${\displaystyle 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

${\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},\Box ,E)}$ , woubäi

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

Informell bedeit:

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

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

Déi follgend Turingmaschinn ${\displaystyle M}$  erwaart eng Rei vun ${\displaystyle a}$ en als Eingabe a verduebelt dës da mat engem Blank (representéiert als o) an der Mëtt:

${\displaystyle M=(\{q_{0},q_{1},q_{2},q_{3},q_{4},q_{e}\},\{a\},\{a,o\},\delta ,q_{0},o,\{q_{e}\})}$ 

${\displaystyle \delta (q_{0},a)=(q_{1},o,R)}$  ${\displaystyle \delta (q_{0},o)=(q_{e},o,N)}$ 

${\displaystyle \delta (q_{1},a)=(q_{1},a,R)}$  ${\displaystyle \delta (q_{1},o)=(q_{2},o,R)}$ 

${\displaystyle \delta (q_{2},o)=(q_{3},a,L)}$  ${\displaystyle \delta (q_{2},a)=(q_{2},a,R)}$ 

${\displaystyle \delta (q_{3},a)=(q_{3},a,L)}$  ${\displaystyle \delta (q_{3},o)=(q_{4},o,L)}$ 

${\displaystyle \delta (q_{4},a)=(q_{4},a,L)}$  ${\displaystyle \delta (q_{4},o)=(q_{0},a,R)}$ 

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

${\displaystyle 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}$  ${\displaystyle \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}$ 

Eng ${\displaystyle k}$ -Band Turingmaschinn besteet aus ${\displaystyle 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 ${\displaystyle k}$ -Band Turingmaschinnen awer net méi mächteg sinn: zou all ${\displaystyle k}$ -Band Maschinn existéiert eng equivalent ${\displaystyle 1}$ -Band Turingmaschinn.

• 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.