Nö, du kannst es ja einfach zur Post bringen. Empfänger unbekannt verzogen, so geht es zumindest bei Briefen.
Nö, du kannst es ja einfach zur Post bringen. Empfänger unbekannt verzogen, so geht es zumindest bei Briefen.
In meiner Vorlesung finde ich es meist ertragreicher (wenn die Zeit es zulässt) ein Thema unterhaltsam zu motivieren. Bevor ich also darauf eingehe, was eine Turing-Maschine ist, versuche ich die Frage, warum man sich damit (oder theoretischer Informatik überhaupt) beschäftigen sollte - insbesondere für diejenigen, die eher weniger damit am Hut haben... - zu animieren. Das funktioniert ganz gut anhand (ein-/d-)er Geschichte:
Unsere Geschichte spielt im Europa der 30er Jahre des letzten Jahrhunderts. Da jede Geschichte einen Bösewicht braucht und wir zu dieser Zeit die Möglichkeit haben, nehmen wir einfach mal den schlimmsten, der uns einfällt:
Achtung Spoiler:
Adolf Hitler. Hitler wollte, wie allgemein bekannt sein dürfte, Europa dem Deutschen Reich einverleiben und seine anitsemitische und faschistische Ideologie weltweit durchsetzen. Hitler war aber augenscheinlich bewusst, dass das in Europa auf wenig Gegenliebe stoßen würde - deshalb ließ er reichsintern verschlüsselt kommunizieren. Als Waffe setzte er dabei auf die Enigma:
Die Enigma ist eine Chiffriermaschine, die in der Reihe der von den Deutschen verwendeten Verschlüsselungsverfahren stand. Für Franzosen und Briten galt die Enigma als "unknackbar" (bei den Polen hatte Marian Rejewski 1932 zwar schon Durchbrüche bei der Entzifferung zu verzeichnen, aber die Polen hatten das Pech, 1938 als erstes Land von den Deutschen überfallen zu werden - außerdem verbesserten die Deutschen die Enigma im Verlauf des Krieges).
Da es damals noch keine Computer gab, stellte sich für die späteren Alliierten die Frage*, ob man überhaupt versuchen sollte, die Enigma zu knacken, oder die damit kodierten Nachrichten möglichst schnell und effizient zu entschlüsseln. Um diese Frage zu beantworten, braucht unsere Geschichte einen Helden:
Alan Turing, britischer Mathematiker und Logiker und Informatiker und so ziemlich alles, weil Wissenschaft damals noch schön überschaubar(er) war. Und da auch der Held eine Waffe braucht, soll auch Turing eine bekommen. Da die Briten damals noch so etwas wie ein Weltreich hatten und dementsprechend an der Weltwirtschaftskrise in den 30er Jahren zu knabbern hatte, können wir uns für Turing leide keine teure Waffe leisten.
Das hier...
Achtung Spoiler:
...muss reichen.
Im Prinzip ist das auch schon alles, was man für eine Turing-Maschine braucht oder was eine Turing-Maschine ist - eine Rolle Klopapier und ein Filzstift
Damit können wir die beiden Kontrahenten gegeneinander antreten lassen...
...und uns mit der Turing-Maschine an sich befassen
* oder hätte sich stellen können - ich war nicht dabei, das ist nur eine Motivation
Sooo, was genau ist jetzt eine Turing-Maschine? Klopapier und Filzstift sind zwar ganz gut, um es sich zu merken, aber in einer Turing-Maschine steckt dann doch etwas mehr - so viel mehr, dass man sie sich nicht mal eben ins Regal stellen kann, sondern sie nur als gedankliches Modell ihr ganzes Potential entfalten kann .
Das liegt einerseits daran, dass die Klopapierrolle in unserer Vorstellung unendlich lang sein soll. Außerdem nennen wir sie nicht länger "Klopapierrolle" (das klingt so, als ob Turing-Maschinen für den Arsch wären, aber Turing-Maschinen sind super ) sondern "Band". Das Band ist unterteilt in "Felder", auf denen mehr oder weniger beliebige Zeichen stehen können.
Den Filzstift nennen wir "Lese-/Schreib-Kopf", denn wir wollen damit nicht nur etwas schreiben, sondern auch nachschauen können, was auf einem Feld steht.
Eine Turing-Maschine arbeitet nun auf folgende Art und Weise:
- Am Anfang steht irgendwo auf dem Band eine sog. "Wort" (effektiv nur eine Folge an Zeichen, also z.B. "10001010" oder "Gööhöhldöaä Älddn897+!n"). Jedes Zeichen steht auf einem eigenen Feld.
- Der Lese-/Schreib-Kopf zeigt auf das erste Zeichen (als nicht auf auf einem Klopapierblatt Feld, das leer ist)
- In jedem Schritt liest der Lese-/Schreib-Kopf, was auf dem aktuellen Feld steht und tut nach einer von uns vorher festgelegten und in Zuständen kodierten Logik folgendes:
- Er lässt das Zeichen stehen, löscht es oder überschreibt es mit einem neuen Zeichen
- Er bewegt sich ein Feld nach links, ein Feld nach rechts oder bleibt auf dem aktuellen Feld
- Die Maschine geht in einen neuen Zustand über
An einem Beispiel kann man sich das besser vor Augen führen. Die "Logik" der Turing-Maschine sei wie folgt gegeben:
Jeder Kreis steht für einen Zustand, jeder Pfeil für einen Übergang. Die Beschriftung eines Pfeils ist wie folgt zu verstehen: wenn die Turing-Maschine in einem Zustand ist und das Zeichen links vom "|" liest, überschreibt es diese mit dem Zeichen rechts vom "|" und bewegt sich nach L(inks), R(echts) oder tut N(ichts). Die Maschine geht dann in den Zustand am Pfeilende über.
Wenn die Maschine also z.B. im Zustand "carry" ist und der Lese-/Schreib-Kopf gerade auf eine 1 zeigt, wird diese mit einer 0 überschrieben und der Lese-/Schreib-Kopf geht ein Feld nach links. Die Maschine bleibt im Zustand "carry".
Der Pfeil aus dem Nichts beim Zustand "start" soll bedeuten, dass in diesem Zustand mit der Abarbeitung begonnen wird. Der Doppelkreis beim Zustand "stop" bedeutet, dass die Maschine anhält, wenn sie diesen Zustand erreicht. Das "eckige u" (sog. Blank-Symbol) beudetet, dass auf dem Feld "nichts" sein soll (aber nichts ist so schwer als Zeichen zu schreiben )
Wenn also am Anfang das Wort "10" auf dem Band steht, der Lese-/Schreibkopf auf die 1 zeigt und die Turing-Maschine (TM) im Startzustand ist, passiert folgendes:
- Die TM liest eine 1, lässt diese stehen, geht einen Schritt nach rechts und zeigt jetzt auf die "0". Sie bleibt im Start-Zustand.
- Die TM liest eine 0, lässt diese stehen, geht einen Schritt nach rechts und zeigt jetzt auf ein leeres Feld. Sie bleibt im Start-Zustand.
- Die TM lässt das Feld leer, geht aber einen Schritt nach links und zeigt wieder auf die "0". Die TM geht in den Zustand "carry" über.
- Die TM liest eine 0, überschreibt sie mit 1 und geht einen Schritt nach Links. Sie wechselt in den Stop-Zustand und beendet die Ausführung.
Auf dem Band steht jetzt "11".
Wer sich die Mühe machen will, kann sich überlegen, was die Maschine tut (Auflösung im Spoiler).
Achtung Spoiler:
Man kann sich eine Turing-Maschine also wie einen Algorithmus oder eine Funktion vorstellen: sie bekommt einen Input (der am Anfang auf dem Band steht) und erzeugt daraus nach festen Regeln schrittweise einen Output (was am Ende auf dem Band steht).
Und das... war's auch schon. Ich hab mir jetzt nicht die Mühe gemacht, alles formal sauber aufzuschreiben, aber die Idee sollte verständlich geworden sein. Obwohl diese Konstruktion sehr einfach ist (im Endeffekt reichen Klopapier und Filzstift) hat man bislang keine "intuitiv" berechenbare Funktion/ Algorithmus gefunden, die man nicht mit einer Turing-Maschine nachbauen könnte. Wenn davon die Rede ist, dass eine Programmiersprache "Turing-vollständig" ist, heißt das im Wesentlichen, dass sie nicht schlechter als eine Rolle Klopapier und ein Filzstift ist.
Man kann auch "Algorithmen, die Algorithmen ausführen" entwerfen (die universelle Turing-Maschine; Betriebssysteme wenn man so will), was auf das Halteproblem führt usw. usf. Da geh ich jetzt nicht weiter darauf ein, der Text wurde schon länger, als geplant
Stattdessen will ich noch auf das Ende der Geschichte eingehen:
Mit Hilfe der Turing-Maschine konnte Turing beantworten, ob Probleme, wie das Knacken der Enigma, lösbar sind oder nur "geschicktes Raten" hilft. Die Antwort lautet...
Achtung Spoiler:
Seine Verdienste (und die der übrigen Codebreaker) hatten trotzdem einen erheblichen Anteil am Sieg der Alliierten über die Nazis. Wenn man sich mit theoretischer Informatik befasst, kann man also Hitler bekämpfen.
Für Turing selbst ist das Ende der Geschichte aber nicht so geil. Zitat Wikipedia:
"Im März 1952 wurde Turing wegen seiner Homosexualität, die damals noch als Straftat verfolgt wurde, zur chemischen Kastration verurteilt. Turing erkrankte in Folge der Hormonbehandlung an einer Depression und starb etwa zwei Jahre später durch Suizid."
tl;dr
Eine Turing-Maschine ist eine Rolle Klopapier und ein Filzstift bzw. ein Algorithmus.
Du hast es zwar sehr schön erklärt und auf eine echt geile Art präsentiert, aber ich raf es trotzdem nicht....
Mein Gehirn kann diesen gedankengängen nicht folgen.
Mir hat beim Schreiben auch die Möglichkeit gefehlt, das gescheit zu animieren. Nur Text find ich auch eher semi-geil
Das Beispiel, das ich benutzt hab, kann man sich hier schrittweise anschauen:
http://turingmachine.io/
In dem Code-Teil oben rechts kann man bei 'input' (2. Zeile) eintragen, was am Anfang auf dem Band stehen soll und dann entweder mit Run den ganzen Durchlauf oder mit Step einzelne Schritte anschauen.
Die Seite hat auch ein paar mehr Beispiele, da bekommt man ein recht gutes Gefühlt für Turing-Maschinen.
Das Thema ist auch nicht leicht zu verstehen, ich hab das irgendwann mal so halbwegs verstanden, aber jetzt gerade konnte ich auch nicht vollständig folgen und habe mich stattdessen gut von der Darstellung unterhalten lassen
Der Film zu Turing ist übrigens auch ganz gut. Ich glaube da scheiden sich die Geister, aber mir hat er gefallen.
Den hab ich noch gar nicht gesehen
Und ja, in der Vorlesung hab ich mir auch über ne Stunde Zeit gelassen, das einzuführen.
Für die absolute Verwirrung hab ich hier noch die formale Definition:
Theoretische Informatiker kann man aber - wenn man ihnen mal über den Weg läuft, die hocken ja meistens in irgendwelchen fensterlosen Kellern - ganz gut damit ärgern, dass sie im Endeffekt nur mit Klopapier und Filzstift arbeiten
Die Waffen wurden hier nicht richtig dargestellt.
Turing führte den Kampf mit Bomben. Nicht mit Turing-Maschinen.
Verstand op nul, frituur op 180.
Ich schätze mal einen Triathleten.