Turingmaschinn
Vu Wikipedia, der fräier Enzyklopedie.
D'Turingmaschinn ass een einfacht mathematescht Modell vun engem Rechenautomat, dat 1936 vum briteschem Mathematiker, Kryptoanalytiker a Computerkonstrukteur Alan Turing definéiert ginn ass. Church-Turing Thees beseet, dat all déi am intuitive Sënn berechebar Funktioune mat enger Turingmaschinn léisbar sinn.
Inhaltsverzeechnes |
[Änneren] Definitioun
[Änneren] 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 beweglechem Lies-/Schreifkapp.
[Änneren] 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 bewegt sech eng Positioun no lénks (L), rechts (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.
[Änneren] Formal Definitioun
Eng Turingmaschinn ass en 7-Tupel
, woubäi
- Q ass den endlechen Ensemble vun Zoustänn,
- Σ ass d'Eingabealphbet,
- Γ ass d'Bandalphabet (
), 
ass d'Iwwergangsfunktioun,
ass de Startzoustand,
steet fir e Blank
ass den endlechen Ensemble vun Endzoustänn
Informell bedeit:
δ(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 
duerch.
[Änneren] Beispill
Déi folgend Turingmaschinn M erwaart eng Rei vun aen als Eingabe a verduebelt dës da mat engem Blank (representéiert als o) an der Mëtt:
<math>M=(\{q_0,q_1,q_2,q_3,q_4,q_e\},\{a\},\{a,o\},\delta,q_0,o,\{q_e\})</math>
<math>\delta(q_0,a)=(q_1,o,R)</math>
<math>\delta(q_0,o)=(q_e,o,N)</math>
<math>\delta(q_1,a)=(q_1,a,R)</math>
<math>\delta(q_1,o)=(q_2,o,R)</math>
<math>\delta(q_2,o)=(q_3,a,L)</math>
<math>\delta(q_2,a)=(q_2,a,R)</math>
<math>\delta(q_3,a)=(q_3,a,L)</math>
<math>\delta(q_3,o)=(q_4,o,L)</math>
<math>\delta(q_4,a)=(q_4,a,L)</math>
<math>\delta(q_4,o)=(q_0,a,R)</math>
Wann d'Maschinn M zum Beispill mat der Eingabe aa gestart gëtt, da stoppt se mat aaoaa um Band. Si mécht folgend Schrëtt:
<math>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</math> <math>\vdash aooq_2a \vdash aooaq_2o \vdash aooq_3aa \vdash aoq_3oaa \vdash aq_4ooaa \vdash aaq_0oaa \vdash aaq_eoaa</math>
[Änneren] 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 vun enee bewegen. 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.
[Änneren] 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.
