Turingmaschinn

Vu Wikipedia
Wiesselen op: Navigatioun, sichen
Turingmaschinn Modell Davey

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

Definitioun[änneren | Quelltext änneren]

Informell Beschreiwung[änneren | Quelltext änneren]

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[änneren | Quelltext änneren]

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 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 a sou weider. D'Berechnung ass fäerdeg, wann d'Kontroll an een Endzoustand gaangen ass.

Formal Definitioun[änneren | Quelltext änneren]

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)

Ass d'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[änneren | Quelltext änneren]

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:

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[änneren | Quelltext änneren]

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

Literatur[änneren | Quelltext änneren]

  • 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[änneren | Quelltext änneren]

Commons: Turingmaschinnen – Biller, Videoen oder Audiodateien