WAHR, ABER UNMÖGLICH ZU BEWEISEN
Stell dir eine Menge von Nachbarn vor, jedes Paar mit seiner eigenen Forderung. Lassen sich alle Forderungen gleichzeitig erfüllen, ist jeder zufrieden. Geraten zwei Forderungen aneinander, muss jemand nachgeben. Physiker, die Magnete aus Quantenspins untersuchen, stehen genau vor dieser Frage. Jedes Paar benachbarter Spins hat eine Energieregel, und das System strebt nach seiner niedrigsten Energie. Wenn ein einziger Zustand jedes Paar zugleich zufriedenstellen kann, heißt das Modell frustrationsfrei (frustration-free).
Solche Modelle sind begehrt. Zu den berühmten Beispielen gehören das AKLT-Modell und Kitaevs torischer Code, Bezugspunkte für exotische Phasen der Materie. Frustrationsfreiheit setzt außerdem enge Grenzen dafür, wie sich ein Material bei niedriger Energie verhalten kann. Daher stellt sich eine naheliegende Frage: Ist das Modell, wenn die Regeln für ein Paar gegeben sind, auf Gittern jeder Größe frustrationsfrei?
Naoto Shiraishi von der Universität Tokio hat diese Frage auf einem quadratischen Gitter aus Spins untersucht, mit derselben Regel zwischen jedem Paar von Nachbarn. Jeder Spin kann d verschiedene Zustände annehmen. Die Antwort besteht aus zwei Teilen, die einander zu widersprechen scheinen.
Ein Gitter genügt
Für jede einzelne Gittergröße ist die Frage gewöhnliche lineare Algebra. Das Problem ist die Unendlichkeit der Größen. Immer größere Gitter zu prüfen, kann ein Scheitern aufdecken, beweist aber nie den Erfolg für alle.
Der erste Satz beseitigt diese Unendlichkeit. Für jeden Wert von d gibt es eine endliche Grenzgröße (cutoff), dieselbe für jede mögliche Regel. Ist ein Modell auf einem Gitter dieser Größe frustrationsfrei, dann ist es auf allen frustrationsfrei. Das Problem ist also entscheidbar: Es gibt einen Algorithmus, der immer mit Ja oder Nein antwortet.
Der Schlüssel ist ein Klassiker der Algebra, der Hilbertsche Basissatz. Die Bedingung bei jeder Größe lässt sich als System polynomialer Gleichungen schreiben, immer in denselben 2d⁴ Unbekannten – den Einträgen der beiden Regelmatrizen. Der Satz garantiert, dass eine unendliche Liste solcher Gleichungen dieselben Lösungen hat wie ein endlicher Teil davon. Da ein frustrationsfreies Gitter auch auf jedem kleineren, daraus ausgeschnittenen Gitter frustrationsfrei bleibt, genügt dann eine einzige Größe.
Das ist kein triviales Ergebnis. Für genau dieselbe Art von Modellen wurde gezeigt, dass eine verwandte Frage – ob es oberhalb des tiefsten Zustands eine Energielücke gibt – unentscheidbar ist, selbst bei festem d.
Ein Kachelsatz, der nach Widersprüchen jagt
Der zweite Satz geht in die andere Richtung. Unter der Annahme, dass die üblichen Axiome der Mathematik, bekannt als ZFC, keinen Widerspruch enthalten, gibt es ein frustrationsfreies Modell, dessen Frustrationsfreiheit sich aus diesen Axiomen nicht beweisen lässt.
Die Konstruktion nutzt Wang-Kacheln: Quadrate mit farbigen Kanten, die ohne Drehung gelegt werden und bei denen Nachbarn zusammenpassen müssen. Für jedes Computerprogramm lässt sich ein endlicher Satz von Kacheln entwerfen, der die gesamte unendliche Ebene bedecken kann, genau dann, wenn das Programm endlos läuft. Jede Kachel wird zu einem Zustand eines Spins. Jedes verbotene Paar benachbarter Kacheln kostet eine Energieeinheit. Das Modell ist genau dann frustrationsfrei, wenn die Kacheln die Ebene bedecken können.
Wähle nun das Programm, das alle möglichen Beweise nach einem Widerspruch in ZFC durchsucht und anhält, wenn es einen findet. Ist ZFC widerspruchsfrei, hält das Programm nie an, und das Modell ist frustrationsfrei. Könnte ZFC das aber beweisen, würde es seine eigene Widerspruchsfreiheit beweisen – was Gödels zweiter Unvollständigkeitssatz verbietet.
Das Modell ist explizit, wenn auch viel zu kompliziert, um es auszuschreiben. Seine Regeln sind nicht einmal wirklich quantenmechanisch: Die Energieterme kommutieren alle, wie einfache klassische Bedingungen.
Eine Grenze, die existiert, aber nicht benannt werden kann
Wie kann ein Problem entscheidbar sein und trotzdem eine Aussage enthalten, die sich nicht beweisen lässt? Die Antwort liegt in der Grenzgröße. Sie ist für jedes d endlich, aber kein Algorithmus kann sie aus d berechnen. Für die Dimension des unbeweisbaren Modells beweisen die Axiome, dass eine endliche Grenzgröße existiert – doch sie können für keine bestimmte Zahl beweisen, dass sie eine solche ist.
Die Grenzgröße wächst außerdem absurd schnell: mindestens so schnell wie die Fleißiger-Biber-Funktion (busy beaver) – die größte Zahl von Markierungen, die ein anhaltendes Programm mit einer gegebenen Zahl von Zuständen auf seinem Band hinterlassen kann –, die jede Funktion übertrifft, die ein Computer berechnen kann. Ihr Wert für Maschinen mit fünf Zuständen wurde laut der Arbeit erst 2024 bestimmt; der Wert für sechs Zustände ist noch unbekannt.
Die Kluft zwischen Existieren und Wissen
Entscheidbarkeit verlangt nur, dass ein korrekter Algorithmus existiert, nicht dass jemand ihn bauen kann. In den meisten vertrauten Fällen spielt der Unterschied keine Rolle. Hier, so argumentiert Shiraishi, wird er zur ganzen Geschichte – und er taucht in einem gewöhnlichen Physikproblem auf einem schlichten quadratischen Gitter auf. Wie Shiraishi angibt, wurde ChatGPT genutzt, um das Entscheidbarkeitsergebnis herzuleiten und zu klären, wie es mit dem Unbeweisbarkeitsergebnis zusammenpasst. Tatsächliche Grenzgrößen zu bestimmen, selbst für sehr kleine Spins, bleibt eine offene Herausforderung.
