COMPUTER KÖNNEN Schach spielen, und seit einigen Jahren schlagen sie regelmässig Grossmeister. Computer unterstützen Chirurgen beim Operieren und verfassen selbstständig Sportnachrichten, indem sie online verfügbare Informationen über Spielort, Spieler und Spielverlauf sowie vorgefertigte Textbausteine zu einem Artikel zusammenschustern. Computer berechnen Aktienkurse und komponieren Basslinien oder gleich ganze Musikstücke. Computer steuern Rangierbahnhöfe und verfassen selbstständig Gedichte. Und natürlich helfen Computer bei der Lösung unzähliger mathematischer Probleme. Können Computer denn alles? Gibt es für sie keine prinzipiellen Schranken?

Betrachten wir, bevor wir hierauf eine vielleicht überraschende Antwort geben, zuerst ein Domino-Spiel. Die Spielsteine, mit denen wir hier spielen, tragen an jedem der beiden Enden eine Zeichenkette. In der oberen Hälfte der Abbildung sind zum Beispiel drei Typen von Spielsteinen vorgestellt, und wir nehmen an, dass von jedem Typus beliebig viele Steine vorrätig sind. Das Ziel des Spieles ist es, Steine hochkant so aneinanderzureihen, dass oben und unten je dieselbe Zahl ablesbar ist. Würde man etwa zuerst einen Stein vom Typ I hinlegen und daran auf der rechten Seite einen Stein vom Typ II und dann einen Stein vom Typ III anfügen, so entstünde oben die Zahl 12331133 und unten die Zahl 12121. Da diese Zahlen verschieden sind, ist der Versuch missglückt. Und sehr bald fällt uns auf, dass das Ziel mit den Steinen der oberen Hälfte der Abbildung unmöglich erreicht werden kann, weil bei all diesen Steinen oben eine längere Zahl notiert ist als unten. Aber wie ist das beim zweiten Spiel in der unteren Hälfte der Abbildung? Ist das Ziel erreichbar? Können Sie Steine so auswählen und aneinanderreihen, dass oben und unten dieselbe Zahl entsteht? Bedenken Sie, dass von jedem Steintyp beliebig viele Steine vorrätig sind.

Der polnisch-US-amerikanische Mathematiker Emil L. Post hat dieses Spiel bereits 1947 eingeführt und beweisen können, dass es niemals von einem Computer gelöst werden kann, egal, wie schnell und raffiniert ausgestattet die Maschine auch sein mag. Ist das nicht verblüffend? Bitte missverstehen Sie das nicht: Ein einzelnes Dominospiel dieser Art mag durchaus von einem Computer gelöst werden, so wie Sie die Lösung vielleicht auch gefunden haben. Aber es ist prinzipiell unmöglich, eine Software herzustellen, die zu jedem beliebigen Set von Steinen dieser Art entscheiden kann, ob das Ziel erreicht werden kann. Heute nicht und in Zukunft nicht. Jede automatisierte Art der Erkenntnisgewinnung, die auf einer streng formalisierten Sprache und Programmanweisungen beruht, ist nicht in der Lage, dieses Problem zu lösen.

Die Möglichkeiten von Computern sind also beschränkt. Seit Emil Post hat man unzählige weitere Probleme entdeckt, die grundsätzlich nicht von Algorithmen gelöst werden können, und sie betreffen teilweise ganz empfindliche und sogar alltagspraktische Bereiche.

Armin P . Barth ist Gymnasiallehrer an der Kantonsschule Baden und Autor. Die Lösung erscheint mit seiner nächsten Kolumne am 6. Juli 2013.

Lösung vom 7. Mai 2013: 17-mal.