Das Physik und Mathematik eng zusammenhängen, ist ja nichts Neues. Dass dieser Zusammenhang aber so eng sein kann, dass man Kernsätze der theoretischen Mathematik, die sich mit den Grenzen der Berechenbarkeit beschäftigen, in physikalischen Modellen wieder finden kann, das ist allerdings schon etwas Neues. Dies zu zeigen ist vor kurzem gelungen. Die zugehörige Arbeit ist in Kurzform (auf 5 Seiten) bei Nature erschienen – das paper, das den kompletten Beweis enthält, gibt es aber auch als Langfassung mit 146 Seiten. (Quellen wie immer am Ende des Artikels.)
Leider ist die Arbeit sehr komplex, abstrakt, und voller Konzepte, die ich nur vage verstehe. Eigentlich sollte mich das vom Bloggen vielleicht abhalten – auf der anderen Seite habe ich nach kurzer Googelei keine einzige einigermaßen ausführliche Erklärung dessen gefunden, was in dieser Arbeit eigentlich passiert. Also versuche ich, zumindest das, was ich so einigermaßen verstanden habe, in diesem Artikel zusammenzupacken. Korrekturen, Ergänzungen, weitere Erläuterungen usw. sind in den Kommentaren sehr gern gesehen, und wenn ihr die Arbeit komplett versteht, dürft ihr auch gern einen Gastartikel für den Blog schreiben. Seid aber auf jeden Fall gewarnt: irgendwo in diesem Blogtext steckt mit an Sicherheit grenzender Wahrscheinlichkeit ein Fehler oder eine Ungenauigkeit.
Da das ganze ziemlich abstrakt ist, bitte ich beim Lesen um etwas Geduld – bevor wir sehen, was eigentlich das physikalische Problem ist, müssen wir uns erst mal mit der den Grundlagen der Mathematik beschäftigen, genauer gesagt, mit Turing-Maschinen. Der Text hier wird also etwas länger werden, aber das ist hier auf dem Blog ja keine Seltenheit… (Aus diesem Grund habe ich auch das neue Feature des Aufteilens in mehrere Seiten verwendet – die Umbrüche sind allerdings an sinnvollen Stellen, nicht willkürlich. Auf dieser Seitegeht’s um die Mathematik und Turing-Maschinen, auf der nächsten um das physikalische Modell und falls ihr euch vor allem für die Konsequenzen interessiert, die gibt es auf der dritten Seite.)
Turing-Maschinen
Turing-Maschinen sind so etwas wie idealisierte Computer. (Achtung: Ich werde im folgenden einiges etwas vereinfachen – zum einen bin ich keine Expertin in Sachen theoretische Mathematik/Informatik, zum anderen sind die Details auch nicht soo wichtig. Und ich hoffe, es stört sich niemand, dass ich manchmal Turing-Maschine mit Bindestrich schreibe und manchmal ohne.) Sie haben einen inneren Zustand (entsprechend zu all dem, was euer Rechner gerade im RAM gespeichert hat, aber bei der Turing-Maschine ist der Zustand bloß eine einzige natürliche Zahl) und einen einfachen Papierstreifen mit Kästchen drauf, in denen entweder gar nichts, eine Null oder eine Eins steht. Ein Lese-Schreib-Kopf liest die Information auf dem Band und kann sie auch überschreiben. Die Maschine startet in einem Zustand und liest das Kästchen, auf das ihr Lese-Schreib-Kopf zeigt. Das Programm das auf der Maschine läuft, besteht aus einer Tabelle, in der für jeden gerade gelesenen Wert und für jeden möglichen Zustand der Maschine festgelegt wird, was sie als nächstes tut: Sie darf den aktuellen Wert auf dem Band überschreiben, sie darf ihren Zustand ändern und sie darf ihren Schreibkopf nach links oder rechts bewegen oder auch stehen bleiben.
Eine einfache Turingmaschine wäre also zum Beispiel MASCHINE A: Beginne im Zustand 1, schreibe eine 0 auf das Band, gehe ein Feld nach rechts, bleibe im Zustand 1. Diese Maschine würde unser ganzes Band mit Nullen vollschreiben (und weil das Band unendlich lang ist, nie fertig werden).
Ein andere Turingmaschine (MASCHINE B) wäre z.B.: Beginne im Zustand 1. Wenn du in diesem Zustand eine 1 liest, wechsle in den Zustand 2, wenn du eine Null liest, dann gehe ein Feld nach rechts. Zustand 2 ist ein Haltezustand. Das ist ein besonderer Zustand, wenn die Maschine ihn erreicht, dann bleibt sie stehe und tut nichts mehr (ihr könnt euch vorstellen, dass irgendwo ne Klingel läutet oder so, damit man das auch merkt.) Diese Maschine liest also das band und hält, wenn sie eine 1 liest – falls auf dem band keine 1 drauf ist, läuft sie immer weiter.
Die Maschine läuft also über das Band, ändert ihren inneren Zustand immer wieder, bis sie irgendwann stehen bleibt, wenn sie einen Haltezustand erreicht – oder eben nicht, wenn die Definition der Maschine keinen Haltezustand vorsieht oder der mit dem gegebenen input nicht erreicht wird (wie bei MASCHINE B, wenn ihr ihr ein band mit lauter Nullen gebt.)
Gegenüber einem realen Computer hat die Turing-Maschine einen Vor- und einen Nachteil. Der Nachteil ist offensichtlich: In so einer simplen Tabellen-Sprache ein Programm wie Matlab oder LaTeX zu schreiben, macht vermutlich wenig Spaß und dürfte ziemlich nervenaufreibend sein. Für praktische Zwecke ist eine Turing-Maschine also nicht so tauglich. Ihr Vorteil – auch gegenüber jedem real existierenden Computer – ist aber, dass das Lese-Schreib-Band unendlich lang ist (unendlich viel Speicherplatz, den könnte ich auch gut gebrauchen…). Wikipedia hat übrigens auch ein schönes Beispiel für eine solche Maschine.
Man kann jetzt eine ganz besondere Turing-Maschine konstruieren, nämlich die “Universelle Turing-Maschine”. Bisher hatte unsere Turing-Maschine ein festes Programm – die universelle Turing-Maschine dagegen kann mit beliebigen Programmen arbeiten. Dazu codieren wir die Tabelle, die angibt, was eine bestimmte Turingmaschine bei welchem Zustand und welchen Eingabedaten tun soll, als eine Abfolge von zeichen, die unsere universelle Turing-Maschine einliest. (Man kann diese Abfolge von Zeichen als eine einzige Zahl zusammenfassen, so dass jede Turingmaschine durch eine Zahl T gekennzeichnet werden kann. Dass das geht ist klar – alles,was in eurem Computer gespeichert ist, besteht aus einer Abfolge von Nullen und Einsen, die man als eine gigantische Zahl auffassen kann.) Die Maschine liest also erst ein Programm ein (das der Turing-Maschine, die wir gerade verwenden wollen) und führt dann dieses Programm aus. (Man kann die universelle Turing-Maschine der Einfachheit halber auch mit einem zweiten Band ausstatten, von dem nur gelesen werden kann und das die Programminformation enthält.) Damit ist die universelle Turing-Maschine also programmierbar und kann jede andere Turing-Maschine nachahmen.
Das Halte-Problem
Jede, die schon einmal programmiert hat, kennt das: Man bastelt irgendeine komplizierte Abfrage oder Entscheidung in das eigene Programm ein, startet es, und nichts passiert – der Rechner durchläuft eine Endlosschleife und nur ein beherztes Drücken von CTRL-C kann ihn daran hindern, dasselbe immer wieder zu tun. Auch eine Turing-Maschine kann in eine Endlos-Schleife geraten, nämlich dann, wenn sie nie einen Zustand erreicht, der als “Haltezustand” definiert wurde – dann läuft sie immer weiter und läuft und läuft und läuft. Das haben wir ja oben schon an den beiden Beispielmaschinen A und B gesehen.
Da Endlosschleifen doof sind, wäre es natürlich schick, man könnte vorher wissen, ob eine bestimmte Turingmaschine anhält oder nicht. Nehmen wir also an (ich halte mich an die Nomenklatur von Wikipedia) wir wollen wissen, ob eine Turingmaschine T (das “T” steht für die Kodierung des Programms der Maschine) in eine Endlosschleife gerät oder nicht, wen wir ihr als Start-Information ein Band mit dem Inhalt w geben (das “w” steht für die Daten, mit denen wir die Maschine füttern).
Was wir brauchen ist also ein Programm, das wir mit der Information T und w füttern und das uns dann die Antwort “Maschine hält” oder “Maschine hält nicht” gibt. Wenn wir also den Code für MASCHINE A eingeben, dann soll das programm, das wir schreiben wollen, den Code der MASCHINE A und das Eingabeband analysieren (das hier egal ist) und sagen “Maschine hält nicht”. Bei MASCHINE B müsste unser programm entsprechend den Code der Maschine analysieren, das band lesen und sagen “Maschine hält”, wenn auf dem Band eine 1 steht, und “Maschine hält nicht”, wenn keine einzige Eins auf dem Band ist.
Falls ihr jetzt denkt “ist doch einfach – ich nehme einfach die Universelle Turing-Maschine, füttere die mit T als Programm und w als Daten und schaue, ob sie anhält”, dann ist das zwar gut gedacht aber zu einfach. Denn wir wollen ja wirklich wissen, ob die Maschine anhält und nicht unendlich lange warten (weil unsere universelle Turingmaschine ja auch nicht zum Ende kommt, wenn es T nicht tut). Anders gesagt: Wir wollen ein Programm, bei dem am Ende die Info “Maschine hält nicht” herauskommen kann. Das Programm selbst (oder unsere universelle Turingmaschine) soll also auf jeden Fall einen Haltezustand erreichen, uns dabei aber die Information “T hält” bzw. “T hält nicht” geben (beispielsweise aufs band schreiben oder durch die Art des Haltezustands – es darf ja auch mehrere Haltezustände geben.)
So eine Maschine kann es aber nicht geben. Der Beweis ist ein bisschen trickreich, ich skizziere nur die Idee. (Details findet ihr bei Wikipedia oder z.B. im Klassiker “Gödel, Escher,Bach” von Hofstadter.) Er beruht darauf, dass unser Vorhersageprogramm ja selbst auch als eine Turingmaschine beschrieben werden kann. Nehmen wir an, dass wir eine Maschine H gefunden haben, die für jedes Eingabepaar (T,w) vorhersagen kann, die Maschine T hält. H liefert also eine eindeutige und richtige Antwort “hält” oder “hält nicht” für jede beliebige Turingmaschine.
Jetzt bauen wir uns eine zweite Maschine G. G verwendet das Programm von H, aber wenn H ausgibt “Maschine hält nicht”, gibt G als Ergebnis eine 1 aus. Wenn H dagegen ausgibt “Maschine hält”, dann springt G in eine Endlosschleife. Und jetzt lässt man die erste Maschine H wiederum auf G los. (Statt den Code T bekommt H also den Code der Maschine G als Eingangsdaten.) Wenn H also herausbekommt, das G hält, dann springt G in eine Endlosschleife. Wenn G in eine Endlosschleife gerät, sollte H ausgeben, dass G nicht hält, also sollte G halten. Da das offensichtlich in sich widersprüchlich ist, kann es die Maschine H nicht geben (denn wenn es sie gäbe, wäre es leicht, aus ihr die Maschine G zu konstruieren.)
Falls ihr das verwirrend findet – ist es auch. Es ist aber für das, was kommt, nicht so wichtig, dass ihr den Beweis versteht. Wichtig ist nur, dass ihr folgende Idee mitnehmt: Turingmaschinen können Berechnungen durchführen, aber es gibt Berechnungen, die auch eine Turingmaschine nicht erfolgreich durchführen kann. Nicht alles, was als mathematische Fragestellung formulierbar ist, ist berechenbar.
Achtung: Streng genommen zeigt das hier erst mal nur, dass eine universelle Turing-Maschine nicht alles berechnen kann. Bisher hat allerdings niemand etwas gefunden, das berechenbar wäre, ohne von einer Turing-Maschine berechenbar zu sein. Die berühmte Church-Turing-Hypothese sagt, dass in der Tat alles, was berechnet werden kann auch von einer Turing-Maschine berechnet werden kann – aber diese Hypothese ist nicht bewiesen und es gibt Leute (z.B. Roger Penrose), die glauben, dass quantenmechanische Prozesse vielleicht Dinge berechnen können, die einer Turing-Maschine nicht zugänglich sind. (Und Penrose verwendet das dann gleich noch, um daraus Schlüsse über unser Bewusstsein und Willensfreiheit usw. abzuleiten, die ich aber alle für vollkommen falsch halte.)
… and now for something completely different…
Kommentare (83)