5. Grenzen des Formalisierens

In diesem Kapitel werden wir Probleme ins Zentrum rücken, die bewiesenermaßen algorithmisch unlösbar sind. Dabei gibt es viele schlechte Nachrichten. Vor ihnen die Augen zu verschließen, wäre nicht sinnvoll, denn es sind keine exotischen Randerscheinungen; sie betreffen vielmehr ganz wichtige und oft sogar alltagspraktische Bereiche. Die Tatsache, dass Turing-Maschinen so überaus einfach sind, wird diese schlechten Nachrichten noch beeindruckender aussehen lassen. Denn wenn wir nachwiesen würden, dass irgendein komplexes und mit zahlreichen Extras ausgestattetes Maschinenmodell nicht in der Lage ist, eine bestimmte Aufgabe zu lösen, wäre das nicht besonders beeindruckend; man könnte sich ja dann immer denken, dass ein anderes Maschinenmodell durchaus dazu in der Lage wäre. Wenn aber ein so elementares Modell wie die Turing-Maschine die Aufgabe nicht lösen kann, dann ist das viel beeindruckender, denn es betrifft alle nur denkbaren Computer, unabhängig von Architektur, Laufzeit, Speicherplatz, Prozessorgeschwindigkeit, und so weiter. Zu zeigen, dass eine bestimmte Aufgabe von einer Turing-Maschine nicht gelöst werden kann, bedeutet, dass sie grundsätzlich nicht algorithmisch lösbar ist, jetzt nicht und in Zukunft nicht, von keinem Computer dieser Welt und mit keiner denkbaren Programmiersprache. Die menschliche Kreativität, die bei einer solchen Aufgabe einzig noch helfen kann, scheint bis heute nicht vollständig mechanisierbar zu sein. Und das ist überaus tröstlich und faszinierend.