Gedanken eines Praktikers zum Turing-Jahr

Die Informatik feiert weltweit Alan Turings 100. Geburtstag. Das Informatik-Spektrum hat Turing im aktuellen Heft (Heft 35,4 (2012)) das Titelbild und mehrere Aufsätze gewidmet. Die Bedeutung Turings für mehrere Teilgebiete der Informatik wird herausgestellt. Turing ist zweifellos wichtig, darüber sind sich Praktiker und Theoretiker einig. Nur sollte er nicht überbewertet werden, oder anders ausgedrückt, er sollte richtig eingeordnet werden. Im Folgenden gebe ich ein paar Gedanken zum Besten, die eventuell dabei helfen können. Als Einstieg will ich zwei Geschichten erzählen. Sie stammen aus meinem eigenen Arbeitsumfeld. Die betroffenen Kollegen sind mir persönlich bekannt.

Episode 1: Ein Kollege von mir hatte auf der Fachhochschule Maschinenbau studiert. Beim Vorstellungsgespräch bei einem Rechnerhersteller im Jahre 1963 erwähnte er, dass er gerade das 1961 erschienene Buch von Hans Hermes über Aufzählbarkeit - Entscheidbarkeit – Berechenbarkeit lesen würde. Da darin die Turing-Maschine vorkam, konnte der Interviewer, ein Mathematiker, nicht umhin zu fragen, ob er auch deren Wesen und Bedeutung für die Informatik erklären könnte. Da er dies offensichtlich konnte, erhielt er ein Angebot für eine Stelle in der Software-Entwicklung. Für beide Seiten, Arbeitgeber und Arbeitnehmer, führte dies zu über 30 Jahren einer zufriedenstellenden Zusammenarbeit. Mein Kollege hat an vielen interessanten und wichtigen Projekten mitgewirkt. Er hat leidenschaftlich gern programmiert und tat es auch nach seiner Pensionierung noch als selbständiger Unternehmer; gebraucht hat er das Wissen über die Turing-Maschine jedoch nie.

Episode 2: In meiner Funktion als Rechenzentrumsleiter wurde ich bereits vor über 50 Jahren mit der Kehrseite der durch (falsch verstandene) Theorie beeinflussten Denkweise konfrontiert. Ich hatte um 1960 einem Mitarbeiter, der seinem Kunden gegenüber erklärte, dass er keine Verantwortung übernehmen könnte für das Terminieren der von ihm geschriebenen Programme. Er war Mathematiker und bezog sich dabei auf Turing. Ich hätte ihn am liebsten auf der Stelle entlassen, wenn dies in Deutschland möglich gewesen wäre. Vielleicht hätte ich es tun sollen. Im Prozess vor dem Arbeitsgericht hätten dann Juristen klären müssen, wie schädlich solche Theorien sein können. Ich ließ es bei einer Ermahnung und Belehrung bewenden. Um die optimale Formulierung dieser Belehrung ringe ich bis heute. Gerne hätte ich Hilfe von der Theoretischen Informatik in Anspruch genommen, nur fand ich bisher keine.

Es folgen jetzt meine eigenen Gedanken zu den aufgeworfenen Fragen. Sie sollten nicht primär als Kritik verstanden werden, sondern eher als Hilferufe. So wie mir, geht es auch einigen andern Kollegen. Ich hoffe meine Ausführungen regen dazu an, bessere Lösungen und Darstellungen zu finden und zur Diskussion zu stellen. Es geht mir nicht darum, die Korrektheit der bisherigen Ergebnisse in Frage zu stellen, noch die Höhe oder die Tiefe – wie immer Sie es sehen wollen - der dahinter stehenden Gedankengänge. Ich möchte vielmehr das Augenmerk auf ihre Relevanz für den Praktiker und ihre Vermittelbarkeit lenken. Wenn etwas wenig Relevanz hat, braucht man sich um die Vermittelbarkeit keine Gedanken zu machen.

Turing-Maschine und Modelle des heutigen Rechnens

Wieso ist ein Papierband mit Strichen, das ich verschieben kann, ein sinnvolles Modell für einen heutigen Computer? So arbeitet doch kein Computer, nicht einmal ein historischer. Das Modell ist weder intuitiv, noch nachvollziehbar. Noch ist es eine Vereinfachung, eine Reduktion auf das Wesentliche. Vor allem, es lässt keinerlei unterschiedliche Abstraktionsstufen zu. Je größer Systeme werden, desto wichtiger sind Abstraktionen.

Die Arbeiten von Turings haben sicher dabei geholfen, einige grundlegende Fragen zu klären, z.B. die der Berechenbarkeit und der Natur von Algorithmen. Auch diente der Begriff ‚Turing-vollständig‘ dazu, die Mindestanforderungen an moderne Rechner festzulegen. Wer fragt jedoch heute noch danach, ob die etwa 100.000 von Google eingesetzten Rechner ‚Turing-vollständig‘ sind, oder die 500.000 von der Firma Robert Bosch verbauten Rechner. Die Gefahr, dass zwei Firmen heute noch in ihrer Werbeschlacht die Mächtigkeit von Rechnerarchitekturen unterschiedlich bewerten, also die Church-Turing-These in Frage stellen, ist äußerst gering.

Nachdem diese Klärung als historische Leistung geschafft wurde, sollten wir uns andern Aufgaben zu wenden, etwa der Korrektheit oder Wohlstrukturiertheit tatsächlicher Programme. Ich selbst bevorzuge für derlei Betrachtungen ein anderes, viel einfacheres Modell. Es ist vielleicht sogar zu einfach (für Theoretiker), dafür aber vielfach verwendbar. Viele Programme, die wir schreiben, stellen Abbildungen zwischen Mengen dar, den Eingabewerten und den Ausgabewerten. Am wichtigsten sind diejenigen Abbildungen, die Mathematiker als Funktionen bezeichnen. Formal lässt sich diese Vorstellung etwa wie folgt ausdrücken:

F: X → Y, wobei  x in X, y in Y und [für alle y l y = f(x)]

Das Wesen einer Abbildung lässt sich sehr gut mit Hilfe einer Tabelle veranschaulichen, in der Eingabe-Symbolen Ausgabe-Symbole gegenüberstellt sind. Mein Parade-Beispiel ist die Umrechnung von römischen in arabische Zahlendarstellungen:

Aus Platzgründen sind die beiden Spalten der Tabelle hier horizontal angeordnet. Man kann erklären, dass man die gesamte Funktion rein tabellarisch darstellen könnte. Bereits bei diesem Beispiel ist es sinnvoller eine Kombination von Algorithmus und Tabelle zu wählen.

Tabellen mit n Spalten (n ≥ 2) oder – um einen mathematischen Ausdruck zu verwenden – Tupelmengen sind das A und O der Informatik. Sie sind der Grundpfeiler. Wer in Tupeln denkt, hat einen verbesserten Zugang zu einer Vielzahl von Problemen. Mit Tabellen lässt sich nicht nur einfach rechnen, sondern auch vieles besser erklären. Mit Tupelmengen ist man bereits mitten drin in modernen Datenbanken, den Relationen des Ted Codd. Bei der Zuordnung von Syntax zu Semantik, der Übersetzung von einer natürlichen Sprache in eine andere, immer sind Abbildungen bzw. Tabellen im Spiel.

Für sehr wichtig halte ich einen weiteren Aspekt. Für viele von uns ist es eine tiefe Einsicht, ein Aha-Effekt. Stellt man sich nämlich Programmläufe als Tupeln vor, so kommt man (gedanklich) ganz einfach zu Testfällen. Es ist ein und dasselbe. Wer eine Transformation nur als Tabelle angibt, braucht nämlich nicht zu testen. Er muss nur sicherstellen, dass er die richtigen Tupel einträgt. Bei der Verifikation tut man gleich das, was sonst allzu leicht vergessen wird. Man fragt, ob man die richtigen Werte genommen hat. Vor allem fragt man sich zu denen durch, die es wissen müssten. Wer eine Tabelle durch Testen verifizieren will, benötigt auch keinen Hinweis auf Edsgar Dijkstra. Wer bei einzelnen Tabelleneinträgen Fehler findet, zieht daraus bestenfalls die Schlussfolgerung möglichst viele Einträge zu testen.

Es gehört zu den Binsenwahrheiten, die jeder Informatiker lernt, dass man Berechnungen durch gespeicherte Werte vermeiden kann und umgekehrt. Bei jeder Rechnergeneration verschiebt sich die Grenze, wo dies sinnvoll ist. Bei endlichen Tabellen, auch wenn sie mehrere Tausend Einträge umfassen, gibt es kein Halteproblem (Näheres dazu weiter unten). Vielleicht gibt es ein Platzproblem. Das kann (besonders bei alten Rechnern) zu Problemen führen. Man wählte daher mit Vorliebe den algorithmischen Ansatz, d.h. man schrieb nicht die Wertepaare auf, sondern eine Formel, mit der Eingabewerte in Ausgabewerte transformiert werden.

Mit Algorithmen müssen sich Informatiker schon noch auseinandersetzten  ̶  leider. Bei Programmen ohne Schleifen oder Rekursion ist alles noch kinderleicht. Erst wenn wir diese beiden Operationen einführen, droht Gefahr. Dort beginnt der Ernst des Lebens. Ab dort ist Informatik nichts mehr für Kinder. Vor allem das Verifizieren und Validieren  ̶   auch Testen genannt  ̶   von iterativen Programmen ist nicht mehr trivial. Sich damit auch theoretisch zu befassen, ist ein sehr wichtiges, aber sehr vernachlässigtes Thema, wenn man einmal vom Stichwort ‚Model Checking‘ absieht.

So wichtig die Verifizierung und Optimierung von Algorithmen im Bereich der Numerik auch ist, sie sind nur ein Teilaspekt dessen, was ein Informatiker benötigt. Für Informatik-Anwendungen der Zukunft sind gute, selbsterklärende Datenbeschreibungen, Datenorganisationen für optimalen Zugriff oder langfristige Sicherung von Datenmengen im Terabyte-Bereich, Bild- und Spracherkennung, semantisches Suchen, sichere Transaktionskonzepte und wiederverwendbare Systemmodelle mindestens ebenso wichtig. Die Beschäftigung mit der Turing-Maschine kann zu all diesen Fragen wenig oder nichts beitragen.

Halteproblem als Grenze

Turing hat 1930 nachgewiesen, dass es nicht möglich ist für beliebige Programme, die auf einem Universalrechner laufen, zu beweisen, dass sie immer zum Halten kommen. Der Beweis dieser Aussage ist eine gedankliche Meisterleistung, einem Taschenspielertrick nicht unähnlich. Er erfolgt durch Diagonalisierung (im Sinne von Cantor). Man nimmt zunächst an, eine bestimmte Aussage gelte und zeigt dann, dass dies – auf sich selbst angewandt – zu einem Widerspruch führt. Der Kern dieses Ergebnisses ist die Feststellung, dass es eine scharfe Grenze zwischen Aufgaben gibt, die berechenbar sind und solchen, die es nicht sind. Es ist eine fundamentale Erkenntnis, ähnlich der von Kurt Gödel über die Unvollständigkeit der Arithmetik. Beide trugen zur Ernüchterung der mathematischen Himmelsstürmer bei, die hofften, dass die Mathematik zu allem klare Aussagen treffen könnte. Andere Klassen von Problemen werden heute vielfach dadurch erledigt, dass gesagt wird, dass sie mindestens so schwierig sind wie das Halte-Problem. Dazu gehört zum Beispiel die Frage, ob zwei verschiedene Programme dieselbe Funktion berechnen.

Jeder Software-Entwickler sollte wissen, dass die Mathematik ihre eigenen Grenzen hat. Noch wichtiger ist es, die Relevanz mathematischer Aussagen zu erkennen, und gegebenenfalls kritisch zu hinterfragen. Als Turing zu seinem Ergebnis gelangte, gab es weder Programmiersprachen, noch Programme. Man benötigt sie auch nicht. Aus pädagogischer Sicht wäre es jedoch hilfreich, es gäbe Beispiele für konkrete Programme, deren Terminierung nicht entscheidbar ist. Mir sind keine bekannt.

Das Halteproblem führt zu einem Dilemma. Dieses ist nicht durch eine falsch verstandene Theorie (wie in Episode 2) verursacht. Es ist grundsätzlicher Art. Für die Masse der Praktiker liegt die tagtägliche Problematik darin, mit einem scheinbaren Konflikt mit der Theorie zu leben. Zumindest ist es ein Graben. Für jedes Programm, das er/sie schreibt, muss er/sie klar sagen, ob es terminiert oder nicht. Einige Programme dürfen nicht terminieren, andere müssen. Etwas anderes als eine klare Verpflichtung ist professionell gesehen unverantwortlich. Man muss sich über Turing hinwegsetzen.

Es ist keine Frage: Jeder Entwickler benötigt Unterstützung, die ihm von Fall zu Fall zeigt, welche Programme terminieren und welche nicht. Mit andern Worten, wir benötigen theoretische Arbeiten, die von unten nach oben fortschreiten, vom einfachen Fall zum Komplexen, von Programmiersprache zu Programmiersprache, von Entwicklungsumgebung zu Entwicklungsumgebung. Dabei lässt die Theorie die Praxis im Stich, und das seit 60 Jahren. Da hilft es auch wenig, wenn Praktikern gesagt wird, dass sie für die Probleme, die sie haben, selbst schuld sind. Es fehle nur die richtige (theoretische) Ausbildung.

Turing-Test als Aufgabe

Es sind vor allem Nicht-Fachleute, die von Turings Beitrag zur KI fasziniert sind. Turing meinte, dass man den Streit darüber, ob Computer denken können, operational beantworten sollte. Er wollte damit den endlosen Debatten, was die beste Definition ist, einen Riegel vorschieben. Deshalb schlug er einen Test vor. Er wird heute Turing-Test genannt. Er sagte nicht, welche Aufgaben zu dem Test gehören. Die Aufgaben sind völlig variabel. Solange ein bestimmtes Ergebnis noch nicht erreicht ist, werden die Aufgaben verändert.

Wenn man schließlich einen Satz von Aufgaben gefunden hat, die jeder Computer genauso gut löst wie jeder Mensch, hört man auf, die Aufgaben zu verändern. Die Aufgaben definieren dann rein operational den Begriff Intelligenz – mehr nicht. Die Philosophie ist voll von Begriffen, wo genaue Definitionen schwer sind. Beispiele sind Bewusstsein, Geist, Leben und Liebe.

Operationale Definitionen gewinnen dadurch, dass sie reduzieren. Wenn ich nicht mehr unterscheiden kann, ob ich es mit einem Menschen oder Computer zu tun habe, folgt daraus noch lange nicht, dass Computer und Mensch das Gleiche sind. Der Computer hat nur einen gewissen Grad an menschlichen Fähigkeiten erreicht.

Theorie ist wichtig

Oft wird die Rolle der Theorie in der Informatik mit der Rolle der Theorie in der Physik gleichgesetzt. Das scheint mir nicht sehr hilfreich zu sein. Ein Vergleich mit der Rolle in den Ingenieurwissenschaften und der Medizin scheint eher angebracht zu sein. Für viele Probleme sind wir Praktiker auf Heuristiken oder Hausmittel angewiesen. Gerne hätten wir gewusst, warum sie funktionieren oder warum andere Dinge nicht funktionieren. Dazu gehört mehr als nur Mathematik.

Für ein Fachgebiet wie die Informatik ist es wichtig, dass Theoretiker nicht ganz in himmlischen Wohnbezirken verbleiben und sich auf grundsätzliche Aussagen in der Art der Mathematik beschränken. Sie müssen herunter kommen und den Praktikern konkrete Hilfe anbieten. Das können Beispiele sein, die zeigen, was geht und was nicht geht, oder Werkzeuge, die helfen, theoretisch schwierige Fragen zu beantworten. Sollte man Theorien entwickeln, die etwas erklären, muss man in Kauf nehmen, dass sie falsifiziert werden können. Natürlich weichen viele Theoretiker deshalb auf Themen aus, die entweder metaphysischen Charakter haben oder reines Notationen-Geplänkel sind. Viele ergötzen sich auch an tollen Spezifikations- oder Programmiersprachen, unbeeindruckt davon, ob je ein Praktiker sie anrührt oder nicht.