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

, woubäi

  ass den endlechen Ensembel vun Zoustänn,
  ass d'Eingabealphbet,
  ass d'Bandalphabet (),
  ass d'Iwwergangsfunktioun,
  ass de Startzoustand,
  steet fir e Blank
  ass den endlechen Ensembel vun Endzoustänn

Informell bedeit:

Wann d'Turingmaschinn  am Zoustand  an dat aktuellt Zeechen  ass, da geet  an den Zoustand  iwwer, iwwerschreift  duerch  a mécht d'Kappbeweegung .

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

Wann d'Maschinn  zum Beispill mat der Eingabe  gestart gëtt, da stoppt se mat  um Band. Si mécht follgend Schrëtt:

 Variante vun Turingmaschinnen 
Eng -Band Turingmaschinn besteet aus  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 -Band Turingmaschinnen awer net méi mächteg sinn: zou all -Band Maschinn existéiert eng equivalent -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 

Kategorie:Theoreetesch Informatik