Montag, 26. September 2011
Mass Quantum suicide
knirps, 22:54h
Notch, der Entwickler von minecraft, hat auf seinem Blog eine interessante, auf der viele-Welten-Theorie basierende Rechenmethode aufgestellt (auch wenn ihm nachher aufgefallen ist, dass er nicht der erste ist, der auf diese Idee kam).
Mit dieser Methode lassen sich nichtdeterministische Probleme in polynomieller Laufzeit auf deterministische Probleme reduzieren. Wer also ein bisschen Ahnung von theoretischer Informatik und Physik hat (wobei afaik die viele-Welten-Theorie in der Physik aus mehreren Gründen abgelehnt wird), wird hieran vielleicht ein wenig Spaß haben.
Grundidee ist folgende (für Laien, so wie mich): Es gibt unendlich viele Universen, und jedes Mal, wenn eine Entscheidung ansteht (z.B. "geht das Photon durch den oberen oder durch den unteren Spalt?") entstehen neue Universen, von denen jedes eine Entscheidungsmöglichkeit enthält. Dazu gibt es das Gedankenexperiment des Quantenselbstmords, nach welchem ein Wissenschaftler aus eigener Perspektive nie stirbt, wenn er in Schrödingers Katzenkiste sitzt, weil er ja nur die Universen beobachtet, in denen er nicht stirbt.
Notch geht da einen Schritt weiter: Was ist, wenn man das komplette Universum in so eine Kiste steckt?
Und hier kommt der Computer ins Spiel. Es ist momentan möglich, jedes nichtdeterministische Problem auf deterministische Probleme zu reduzieren, indem man es in zwei Teile teilt: einen nichtdeterm. "Rateteil", in dem die Lösung geraten wird, und den determin. Verifizierungsteil, in dem diese Lösung auf Richtigkeit verifiziert wird. Der letzte Teil ist für NP-Probleme in polynomieller Laufzeit machbar, der erste Teil ist in vielen Fällen nur mit exponentieller Laufzeit deterministisch simulierbar.
Kombiniert ergibt das: Rate eine Lösung, verifiziere sie, wenn sie falsch ist, zerstöre das Universum. So überleben nur Universen, in denen die Lösung richtig ist, also werden nur richtige Lösungen beobachtet, die alle in polynom. Zeit berechnet wurden. Coole Sache.
Mit dieser Methode lassen sich nichtdeterministische Probleme in polynomieller Laufzeit auf deterministische Probleme reduzieren. Wer also ein bisschen Ahnung von theoretischer Informatik und Physik hat (wobei afaik die viele-Welten-Theorie in der Physik aus mehreren Gründen abgelehnt wird), wird hieran vielleicht ein wenig Spaß haben.
Grundidee ist folgende (für Laien, so wie mich): Es gibt unendlich viele Universen, und jedes Mal, wenn eine Entscheidung ansteht (z.B. "geht das Photon durch den oberen oder durch den unteren Spalt?") entstehen neue Universen, von denen jedes eine Entscheidungsmöglichkeit enthält. Dazu gibt es das Gedankenexperiment des Quantenselbstmords, nach welchem ein Wissenschaftler aus eigener Perspektive nie stirbt, wenn er in Schrödingers Katzenkiste sitzt, weil er ja nur die Universen beobachtet, in denen er nicht stirbt.
Notch geht da einen Schritt weiter: Was ist, wenn man das komplette Universum in so eine Kiste steckt?
Und hier kommt der Computer ins Spiel. Es ist momentan möglich, jedes nichtdeterministische Problem auf deterministische Probleme zu reduzieren, indem man es in zwei Teile teilt: einen nichtdeterm. "Rateteil", in dem die Lösung geraten wird, und den determin. Verifizierungsteil, in dem diese Lösung auf Richtigkeit verifiziert wird. Der letzte Teil ist für NP-Probleme in polynomieller Laufzeit machbar, der erste Teil ist in vielen Fällen nur mit exponentieller Laufzeit deterministisch simulierbar.
Kombiniert ergibt das: Rate eine Lösung, verifiziere sie, wenn sie falsch ist, zerstöre das Universum. So überleben nur Universen, in denen die Lösung richtig ist, also werden nur richtige Lösungen beobachtet, die alle in polynom. Zeit berechnet wurden. Coole Sache.
... comment
