Mittwoch, 24. Oktober 2007Wolframs 2,3 TM ist universell!Ich glaubs ja kaum. Stephen Wolfram hat 2004 eine Turingmaschine entworfen und 25000$ für einen Beweis ausgelobt, der die Universalität entscheidet. Heute, am gleichen Tag an dem ich zufällig meinen Beitrag über Universelle Turingmaschinen geschrieben habe kommt das rein: Wolfram's 2,3 Turing Machine Is Universal! (Beweis) Damit ist es die kleinste bekannte universelle Turingmaschine. Hier gibts technische Details.
Wolframs 2,3 TM ist universell! Geschrieben von Turing
in Informatik um
18:25
Kommentare (0) Trackbacks (0) Tags für diesen Artikel: entscheidbarkeitstheorie, informatik, tm, turing-maschine, universelle turingmaschinen, utm
Mittwoch, 24. Oktober 2007Universelle TuringmaschinenVielleicht erinnert sich noch jemand, dass ich in grauer Vorzeit mal eine Serie über Automatentheorie gestartet habe, mit dem Ziel, irgendwann zur Entscheidbarkeitstheorie zu gelangen. Der Grund, warum ich das nie weitergeführt habe ist, dass ich Automatentheorie nicht besonders spannend finde. Also überspringe ich den langweiligen Teil, komme direkt wieder zu Turingmaschinen und schreibe vielleicht später einen Beitrag über Automatentheorie mit einem eher zusammenfassenderen Charakter. Entscheidbarkeitstheorie also. Die meisten Probleme sind ja irgendwie durch eine konkrete Fragestellung motiviert. Hier ist diese Frage, welche Funktionen entschieden werden können und welche nicht. Ich werde noch darauf kommen was das im Detail bedeutet. Erstmal führen wir eine neue Art Turingmaschine ein, die wir später brauchen. Eine Turingmaschine, nennen wir sie M, ist ja folgendermaßen definiert: Dabei ist Q die Menge der Zustände und q0 identifiziert den Startzustand. So eine gewöhnliche Turingmaschine hat einen gewaltigen Nachteil. Sie ist mit der formalen Definition bereits vollständig programmiert. Und zwar endgültig. Viel schöner und vertrauter wäre es doch, wenn eine Turingmaschine nur die "Hardware" zur Verfügung stellen würde und wir das Programm auf das Band schreiben könnten, genau wie wir das bei normalen Computern tun. Da schreiben wir das Programm auf die Festplatte (genauer gesagt in den Bootsektor) und von da aus guckt unser Computer nur, welches Programm an der richtigen Stelle der Festplatte zur Ausführung bereit liegt. Man stelle sich vor, wir würden für jeden auszuführenden Algorithmus einen neuen Prozessor kaufen und dem nur die Instanzen füttern. Ein Sortierprozessor zum Beispiel, dem wir nur Ganzzahlen zum Sortieren geben könnten, oder ein "Fülle-den-Cache-mit-Daten-Prozessor". Im echten Leben mutet das absurd an, aber so machen es klassische Turingmaschinen und für die Theorie kann man das auch tun. Aber es geht eben auch anders, und das nennt man eine "universelle Turingmaschine", kurz UTM, noch kürzer U. Diese kann ein beliebiges Programm (bzw. eine andere, normale Turingmaschine M) ausführen. Die Eingabe besteht jetzt nicht mehr aus einem Wort w, sondern aus (<M>w). Dabei ist w nach wie vor das zu bearbeitende Wort, neu ist <M>, die so genannte Gödelnummer der zu simulierenden Turingmaschine M. Man kann jede normale TM in eine lange Zahl codieren, die dann wiederum eindeutig ist. Zu jeder Gödelnummer gehört genau eine Turingmaschine. Diese Nummer wiederum gibt man dann als Eingabe an die UTM, die dann die zur Gödelnummer zugehörige TM simuliert. Diese Codierung funktioniert so:
Keine Erklärung nötig soweit? Doch? Na gut. Zuerst transferieren wir das Bandalphabet (hier oBdA {0,1,B}) in Und das ist ja schließlich unser Ziel gewesen. Nun, die universelle TM hat allerdings auch nur ein {0,1} Alphabet, deshalb notiert man einen einzelnen Zustandsübergang so: Jetzt dienen die Einsen als "Trenner" für eine Anzahl von Nullen, die mit dem ursprünglichen Zustandsübergang korrespondiert. Ein alter Übergang Wo wir uns jetzt diese ganze Arbeit gemacht haben, können wir damit endlich wieder auf die Gödelnummer zurück kommen. Die sieht jetzt nämlich so aus: 111 code(1) 11 code(2) 11 ... 11 code(n-1) 11 code(n) 111 Drei Einsen markieren also Start und Ende der Gödelnummer, zwei Einsen trennen zwei Codierungen für die Übergänge. Das Ziel ist erreicht, die Turingmaschine wird in einer langen, langen Nummer notiert, die offensichtlich auch wieder in die entsprechende Maschine zurück rechnen lässt. Wenn wir jetzt eine solche Gödelnummer, zusammen mit dem zu entscheidenden Wort an die UTM übergeben, kann diese Schritt für Schritt die Gödelnummer lesen, den neuen Zustand (und damit die neue Position in der Gödelnummer) berechnen und am Ende entscheiden, ob das Wort akzeptiert wird oder nicht. Wie das genau funktioniert wollt ihr nicht wissen, die Gödelnummerkonstruktion war ja schon etwas unheimlich. Nur so viel: Man kann Turingmaschinen auch mit mehreren Speicherbändern definieren. Davon nehmen wir uns in diesem Fall drei, schreiben die zu simulierende Gödelnummer auf das erste, das Wort auf das zweite und auf das dritte kommt der aktuelle Zustand der zu simulierenden TM. Dann wird die Programmierung der UTM zwar weniger hässlich, aber nicht viel. Bleibt die Frage nach der Rechenzeit. Wenn man sich die Rechenoperationen der UTM allerdings genau anschaut, wird schnell klar, dass die aufwändigste Operation die Suche nach der neuen Position in der Gödelnummer ist. Die UTM ist damit nur konstant langsamer als die ursprüngliche TM, hier droht also keine exponentielle Gefahr, außer die ursprüngliche TM war eh schon exponentiell langsam. So weit, so gut. Wir haben gesehen, dass man eine TM auch als lange Nummer schreiben kann. Außerdem gibt es offensichtliche eine universelle Turingmaschine, die mit dieser Nummer und dem zu entscheidenden Wort diese TM simulieren kann. Benutzen kann man das für... ääh... eigentlich kann man das nicht benutzen. Man braucht es lediglich später für einen wichtigen Beweis. Ist theoretische Informatik nicht schön? Wer hier aber dringend eine "Auflösung" braucht, der kann sich ja damit behelfen, dass die UTM offenbar eine praxisnähere Version von Turingmaschinen darstellt, denn man kann sie (auf aufwändige Art und weise) programmieren und muss sich nicht für jeden Algorithmus eine neue Turingmaschine kaufen. Gott sei dank. Update: Übrigens..
Universelle Turingmaschinen Geschrieben von Turing
in Informatik um
07:49
Kommentare (0) Trackbacks (0) Tags für diesen Artikel: entscheidbarkeitstheorie, halteproblem, informatik, tm, turing-maschine, universelle turingmaschinen, utm
|
KategorienFeedsGetaggte Artikelööh.. informatik?
algorithmus china determinismus entscheidbarkeitstheorie fehlerwahrscheinlichkeit fernsehen filme formale sprachen games geek-zeug informatik komplexitã¤t komplexitã¤tsklasse laufzeit linux medien millenium-probleme monty hall nichtdeterminismus nicht eingã¤ngig nintendo ds np o-notation p poker p vs. np randomisierung rffc RP sco sonstiges sonstiges mathematisches spieltheorie statik technische mechanik tm turing turing-maschine universelle turingmaschinen utm videospiele wachstum wahrscheinlichkeit xkcd zpp SonstigesBlogrollSuche |
Powered by s9y - Design by Lordcoffee