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

Ass d'Turingmaschinn am Zoustand an dat aktuellt Zeechen ass , da geet an den Zoustand iwwer, iwwerschreift duerch a féiert Kappbewegung duerch.

Beispill[änneren | Quelltext änneren]

Déi folgend 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 folgend Schrëtt:

Variante vun Turingmaschinnen[änneren | Quelltext ä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 bewegen. 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 | 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