Der Satz von Turing

Visits: 1862

Alan Turing

 

 

Philipp Wehrli, 21. Juli 2006
Von einer mathematischen Sprache erwarten wir, dass alle Begriffe eindeutig definiert sind und dass entscheidbar ist, ob eine Ansammlung von Zeichen einen Begriff definiert oder ob es sich nur um eine bedeutungsleere Anordnung von Zeichen handelt. Der Satz von Turing zeigt, dass kein Verfahren gibt, mit dem saubere mathematische Definitionen von bedeutungsleeren Zeichenanhäufungen unterschieden werden können. Mathematik kann deshalb nie absolut exakt sein, weil schon ihre Grundlage, die Definitionen und Axiome, unsicher sind.

Dieser Artikel benützt die im Artikel Cantors Unendlichkeit erklärten mathematischen Methoden und Begriffe, insbesondere Cantors Diagonalverfahren.

Der Satz von Turing ist einfacher zu beweisen und meiner Ansicht nach tiefgründiger als der berühmte Unvollständigkeitssatz von Kurt Gödel. Ich stelle zuerst eine Überlegung vor, die mir selber im Januar 1999 einfiel, drei Jahre bevor ich von Turings Satz Kenntnis hatte. Die Schlussfolgerung und insbesondere der Beweis stimmen praktisch wörtlich mit Turings Satz überein, sind aber weniger mathematisch und zeigen daher auch besser, dass es sich hier um ein grundsätzliches sprachliches Problem handelt. Jedes sprachliche System enthält unpräzise Definitionen und es gibt keine allgemeine Methode um festzustellen, welche der verwendeten Definitionen unpräzise sind.

Eine linguistische Variante von Turings Satz

Cantor zeigte mit seinem Diagonalverfahren, dass die Menge der reellen Zahlen überabzählbar ist. Ich habe mich gefragt, woher denn die überzählbar vielen Zahlen kommen? Sicher gehören die natürlichen Zahlen und die Brüche zur Menge der reellen Zahlen. Aber diese sind bekanntlich abzählbar. Weiter kommen die Wurzeln dazu. Auch von diesen gibt es unendlich viele, aber auch die Wurzeln sind abzählbar. Wenn ich abzählbar viele abzählbare Mengen vereinige, so muss die Vereinigung wieder abzählbar sein. Was gibt es noch für reelle Zahlen? Irgendwo müssen doch die überabzählbar unendlich vielen Zahlen sein! Die Kreiszahl Pi und die Eulersche Zahl e fielen mir noch ein. Ach, so: Alle Zahlen, die sich irgendwie durch Reihen beschreiben lassen. Wie viele gibt es davon wohl? Gibt es noch andere Möglichkeiten, eine reelle Zahl zu definieren?

Da fiel mir plötzlich folgendes auf: In der Mathematik wird nur eine endliche Anzahl verschiedener Zeichen verwendet. Eine mathematische Definition besteht aus einer endlich langen Folge dieser endlich vielen Zeichen. Diese endlich langen Folgen kann ich aber der Länge nach sortiert und alphabetisch geordnet auflisten. Zuerst kommen alle Folgen, die aus nur einem Zeichen bestehen, dann alle mit zwei Zeichen u. s. w. Alle endlich lagen Sätze, die mit den mathematischen Zeichen formuliert werden können, sind in dieser Liste enthalten! Die Liste enthält zwar auch ziemlich viel sinnloses Zeugs, aber alle sauberen mathematischen Definitionen sind in der Liste drin!

Wenn aber alle Definitionen in der Liste enthalten sind, dann sind auch alle Definitionen von reellen Zahlen in der Liste drin. Kein noch so brillanter Mathematiker kann eine reelle Zahl definieren, die nicht schon längst in meiner Liste definiert ist. Denn meine Liste enthält alle Definitionen. Cantor behauptete, er könne zu jeder Liste von reellen Zahlen eine reelle Zahl definieren, die nicht in der Liste enthalten sei. Kann gar nicht sein bei meiner Liste! Denn in meiner Liste steht alles drin, was Cantor in seinem ganzen Leben gesagt und geschrieben hat. Und irgendwo, sagen wir an Stelle X, steht da auch: Nimm Philipp Wehrlis Liste und wende Cantors Diagonalverfahren an. Was geschieht dann an dieser Stelle? Definiert der Satz X eine reelle Zahl? Wo ist der Haken?

Meine Idee war: Jede reelle Zahl, die sauber definiert werden kann, ist in meiner Liste enthalten. Weshalb sollen wir uns mit überabzählbar vielen reellen Zahlen herumschlagen, wenn die meisten von ihnen nicht einmal eindeutig definiert werden können? Streichen wir einfach alle weg, die nicht in der Liste stehen! Nur die Zahlen sollen ‚reell’ heissen, die in einem endlich langen Satz definiert werden können.

Dies hätte zwei Vorteile: Erstens wären dies nur abzählbar viele. Denn sie sind ja in meiner Liste der endlichen Zeichenfolgen enthalten. Zweitens könnte sicher niemand eine reelle Zahl definieren, die nicht schon in der Liste der Definitionen enthalten ist. Dies scheint ein Widerspruch zu Cantors Satz zu sein. Ich hätte eine Liste von reellen Zahlen und niemand könnte eine reelle Zahl nennen, die nicht schon in der Liste steht.

Einen kleinen Haken hat die Sache noch. Ich habe ja nicht eine Liste von reellen Zahlen. Ich habe nur eine Liste von Zeichenfolgen. Viele dieser Zeichenfolgen haben überhaupt nicht mit reellen Zahlen zu tun, sie sind völlig bedeutungslos. Ich muss also zuerst die bedeutungslosen Zeichenfolgen wegstreichen.

Ich habe angenommen, dies sei möglich. Aber wenn ich die bedeutungslosen Zeichenfolgen wegstreichen könnte, dann ergäbe sich ein Widerspruch. Dann hätte ich nämlich wie beschrieben eine Liste von reellen Zahlen zu der niemand eine reelle Zahl hinzufügen könnte. Aber wie Cantors Satz zeigt, ist dies nicht möglich. Meine Annahme ist also falsch: Es ist nicht möglich, die bedeutungslosen Zeichenfolgen von den sauberen mathematischen Definitionen zu unterscheiden.

tremendously deep

Ich weiss nicht, ob Sie nach dieser Lektüre ruhig schlafen können. Turings Satz gehört zum Abgrundtiefsten, was die Mathematik zu bieten hat. Bertrand Russell schrieb, er habe mehrere Wochen lang kaum gegessen, als er sich mit diesen Fragen befasste. Ich kann ihm hier durchaus nachfühlen. Keine Erkenntnis hat mich mehr erschüttert als diese. Gregory J. Chaitin, der einen eng verwandten Satz entdeckte, schreibt: „Turing’s work is tremendously deep.“ (Cha 1)

tremendously, also schrecklich, furchtbar, kolossal, riesig, fürchterlich, ungeheuer; verwandt mit tremulous: zitternd, bebend. Weshalb braucht ein Mathematiker solch ein Wort?

Turings Satz trifft eine göttliche Frage. Eine von Gottes wichtigsten Eigenschaften ist seine Allwissenheit. Auch wenn ein Mathematiker nicht an Gott glaubt, so erlebt er doch ein religiöses Gefühl, wenn ihm eine neue Erkenntnis einfällt. Mathematiker fühlen sich in der Logik geborgen. Logik ist wahr, treu, zuverlässig, ehrlich. Logik ist der sichere Halt in einer unsicheren Welt.

Turings Satz bringt die Logik ins Wanken und damit wankt die Welt. Manche Menschen können dies schwer nachvollziehen. Wer aus dem Alltag gewohnt ist, dass die eigene Logik immer mal wieder versagt, findet nichts daran, dass die Möglichkeiten der Logik begrenzt sind. Aber Männer wie Gödel, Cantor und Turing waren sich gewohnt, dass sie sich auf ihre Logik verlassen konnten. Sie machten sicher eine ganze Reihe menschlicher Fehler in ihrem Leben. Aber sie machten keine Fehler in der Logik. Auf die Logik war Verlass. Es war ein fürchterlicher Schock, dass diese Stütze wankte. Ja, nicht nur die Logik entpuppte sich als unsicher, schon die Grundlagen der Logik, die Definitionen wankten. Sie wankten nicht, weil der menschliche Geist unvollkommen war und Fehler machte. Auch Gott selbst wäre dieser Einschränkung unterworfen. Es gibt keine Allwissenheit, denn die Logik hat Grenzen. Turing hat das Höchste erreicht, was man mit Logik erreichen kann: Er hat mit Logik die Grenzen der Logik gezeigt.

Turings Satz und das Halteproblem

In meiner Darstellung werden die reellen Zahlen durch endliche Folgen von mathematischen Zeichen definiert. Ich gehe davon aus, dass jemand diese Zeichenfolgen auch lesen und interpretieren kann. Aber ich zeige, dass niemand bedeutungsleere Folgen von mathematischen Definitionen eindeutig unterscheiden kann.

Im Unterschied dazu interessierte sich Turing als Vater des Computers für Computerprogramme. Er betrachtete nicht schriftliche Definitionen, sondern Computerprogramme, die je eine reelle Zahl produzierten. Er dachte sich alle überhaupt möglichen Computerprogramme aufgelistet, so wie ich die Zeichenfolgen aufgelistet dachte.

Nun wendet er wie ich oben Cantors Diagonalverfahren an, um eine Zahl x zu produzieren. Damit das Diagonalverfahren angewendet werden kann, muss das N-te Programm entweder anhalten, weil es einen Error produziert oder es muss in endlicher Zeit die N-te Dezimalstelle der reellen Zahl ausspucken und dann anhalten. Wenn aber alle Programme auf die eine oder andere Weise anhalten würden, dann würde sich wie oben ein Widerspruch ergeben. Denn dann hätten wir ja einen Computer, der eine reelle Zahl berechnet, die mit keinem Programm berechnet werden kann. Turing schliesst daraus, dass der Computer bei gewissen Programmen nie anhält, dass also gewisse mathematisch korrekt formulierte Fragen nicht entscheidbar sind.

Mit dieser Erkenntnis war ein grosser Traum der Mathematiker gestorben. Worum ging es? Auf dem 2. Internationalen Mathematikerkongress im Jahre 1900 in Paris nannte David Hilbert dreiundzwanzig mathematische Probleme, die er als Schlüsselprobleme für den weiteren Fortschritt ansah. Es zeigte sich dann im Verlauf des 20. Jahrhunderts tatsächlich, dass Hilbert fast durchgängig Kernprobleme der Mathematik genannt hatte. Als zehntes Problem formulierte er das sogenannte Entscheidungsproblem:

Eine Gleichung mit irgendwelchen Unbekannten und mit ganzen rationalen Zahlenkoeffizienten sei vorgelegt: Man soll ein Verfahren angeben, nach welchem sich mittels einer endlichen Anzahl von Operationen entscheiden lässt, ob die Gleichung in ganzen Zahlen lösbar ist.

Genau dies hatte Turing versucht: Ein Computer sollte eine natürliche Zahl berechnen, nämlich eine bestimmte Dezimalstelle einer reellen Zahl. Falls diese Zahl nicht berechnet werden kann, soll der Computer das bemerken und anhalten. Turing hatte Hilberts Entscheidungsproblem in das Halteproblem umformuliert und gezeigt, dass kein Computer das Geforderte leisten kann, weil dies grundsätzlich nicht möglich ist. Was ist so schlimm daran?

Beim Entscheidungsproblem geht es um eine grundsätzliche Frage. Die Frage ist: Gibt es ein Verfahren, mit dem alle Probleme der Mathematik (die zu einer entsprechend wohldefinierten Klasse gehören) eines nach dem anderen gelöst werden können? Wenn wir so ein Verfahren finden würden, dann wäre die Mathematik ein für allemal abgeschlossen. Die Probleme wären grundsätzlich gelöst, alles weitere wäre Rechenarbeit, die auch ein Computer erledigen könnte. Die Frage ist auch, was Mathematik überhaupt ist. Ist Mathematik ein abgeschlossenes System von Aussagen, von denen jede entweder wahr oder falsch ist? Ist jede Gleichung entweder lösbar oder unlösbar? Diese Fragen betreffen nicht nur ein Randgebiet der Mathematik, sondern die gesamte Logik. Selbst in einem sehr strengen Rahmen der Logik lässt sich nicht jede Frage mit ja oder nein beantworten. Selbst das intelligenteste und allwissendste Lebewesen kann nicht jede Frage beantworten. Es gibt in der Welt Fragen, auf die es keine Antwort gibt, obwohl die Fragen durchaus korrekt und vernünftig gestellt sind.

Eine detaillierte Erklärung zu Turings Überlegungen gibt (Pen 1). Einige weitere ähnliche Probleme und einige Computerprogramme, die das Halteproblem illustrieren, beschreibt (Cha 1).

Weitere Texte zum Thema Grenzen der Mathematik und der Erkenntnis:

Deduktion – Macht und Grenzen der Mathematik
Der kartesische Dämon