Proof Assistant

Proof Assistant

Ein Proof Assistant ist ein Programm, das mathematische Beweise nicht nur aufschreibt, sondern Schritt für Schritt maschinell überprüft. Damit lassen sich Fehler in Beweisen und in sicherheitskritischer Software finden, die Menschen übersehen würden.

Ein Proof Assistant ist ein Programm, das mathematische Beweise überprüft. Man formuliert einen Beweis in einer formalen Sprache — einer Sprache, in der jeder Schritt so präzise ist, dass eine Maschine ihn eindeutig lesen kann. Der Proof Assistant prüft dann jeden einzelnen Schluss: Folgt Schritt drei wirklich aus Schritt zwei? Stimmt die Logik bis zum Ende? Ein Mensch kann hundert Seiten Beweis durchlesen und dabei einen winzigen Fehler übersehen. Das Programm macht das nicht. Es akzeptiert einen Beweis nur dann, wenn er vollständig korrekt ist — kein einziger Schritt darf fehlen oder ungültig sein.

Warum mathematische Korrektheit so schwer zu garantieren ist

Mathematische Beweise können sehr lang und verschachtelt sein. Der Beweis des Vier-Farben-Satzes — der besagt, dass man jede Landkarte mit vier Farben einfärben kann, ohne dass zwei benachbarte Länder dieselbe Farbe haben — umfasst Tausende Fälle. Als er 1976 erschien, zweifelte die Fachwelt jahrzehntelang daran, ob er wirklich lückenlos war. Ein Proof Assistant löst dieses Problem grundsätzlich: Entweder der Beweis wird vollständig akzeptiert, oder er wird abgelehnt. Graubereiche gibt es nicht.

Dasselbe gilt für Software. Ein Programm ist im Kern eine Folge von Anweisungen, und man kann mathematisch beweisen, dass ein Programm genau das tut, was es soll — und nichts anderes. Für Software, die in Flugzeugsteuerungen, Herzschrittmachern oder Verschlüsselungssystemen läuft, ist das keine akademische Spielerei. Ein übersehener Fehler kann dort echten Schaden anrichten.

Wie man mit einem Proof Assistant arbeitet

Man gibt dem Proof Assistant zunächst eine Aussage, die man beweisen möchte — zum Beispiel: « Die Summe zweier gerader Zahlen ist immer gerade. » Dann baut man den Beweis Schritt für Schritt auf, in der formalen Sprache des Systems. Nach jedem Schritt zeigt der Proof Assistant, was noch zu beweisen übrig bleibt. Dieses offene Ziel nennt man ein Proof Goal. Man bearbeitet es, bis nichts mehr übrig ist.

Der Prozess ist interaktiv: Das Programm ist kein Automat, der selbst Beweise erfindet. Es ist eher ein strenger Korrektor, der jeden Schritt abnimmt und sofort meldet, wenn etwas nicht stimmt. Manche Proof Assistants haben inzwischen Taktiken eingebaut, die kleine Teilschritte automatisch erledigen. Den eigentlichen Beweis denkt sich aber nach wie vor der Mensch aus.

Die bekanntesten Systeme heißen Lean, Coq und Isabelle. Sie unterscheiden sich vor allem in ihrer formalen Sprache und darin, welche Arten von Beweisen besonders gut unterstützt werden. Lean hat in den letzten Jahren viel Aufmerksamkeit bekommen, weil eine wachsende Gemeinschaft von Mathematikern aktuelle Forschungsergebnisse darin formalisiert.

Proof Assistants in aktuellen KI-Debatten

In der KI-Forschung gelten Proof Assistants gerade als ein möglicher Weg, große Sprachmodelle verlässlicher zu machen. Das Problem: Ein Sprachmodell wie ein Chatbot kann überzeugend klingende Lösungen für Mathematikaufgaben schreiben, die trotzdem falsch sind. Koppelt man das Modell an einen Proof Assistant, kann der Assistent jede vorgeschlagene Lösung sofort maschinell prüfen. Falsche Antworten werden automatisch aussortiert.

OpenAI, Google DeepMind und andere Labore arbeiten an Systemen, die genau das tun. DeepMinds Modell AlphaProof löste 2024 mehrere Aufgaben der Internationalen Mathematikolympiade, indem es Lösungsideen generierte und sie direkt in Lean überprüfte. Das ist kein klassischer Proof Assistant mehr, aber ohne ihn wäre es nicht möglich gewesen.

Für die breitere Tech-Industrie ist das relevant, weil verifizierte Software und verifizierte KI-Ausgaben ein wachsendes Thema in der Regulierung werden. Wer beweisen kann, dass sein System korrekt arbeitet, hat gegenüber Aufsichtsbehörden einen handfesten Vorteil gegenüber jemandem, der nur sagt: « Wir haben es gut getestet. »

Subscribe free. Unsubscribe the second it sucks.

High-signal news across AI, business, UX, and tech. Every morning.