Turingmaschinn

Eng Turingmaschinn ass een einfache mathematesche Modell vun engem Rechenautomat, dee 1936 vum britesche Mathematiker, Kryptoanalytiker a Computerkonstrukteur 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.

Turingmaschinn Modell Davey

DefinitiounÄnneren

Informell BeschreiwungÄ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 beweegleche Lies-/Schreifkapp.

AarbechtsweisÄnneren

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Änneren

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Änneren

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Änneren

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

Commons: Turingmaschinnen – Biller, Videoen oder Audiodateien