Von der Berechenbarkeit zum modernen Computer

Kurt Gödel, Logiker

Kurt Gödel (1906–1978) war ein österreichischer Mathematiker und einer der bedeutendsten Logiker des 20. Jahrhunderts. 1940 entschloss er sich, Österreich für immer zu verlassen und in die USA auszuwandern. Er fand in Princeton am neu gegründeten Institute for Advanced Study eine für ihn passende und höchst förderliche Atmosphäre sowie eine neue Heimat.

Gödel studierte an der Universität Wien ab 1924 Mathematik und wurde ein Mitglied des Wiener Kreises, in den ihn sein Lehrer, der Wiener Mathematiker Hans Hahn, einführte. Zu seiner Studienzeit waren die Grundlagen der Mathematik und der Logik ein heiß diskutiertes Thema. Welches Axiomensystem soll man auswählen? Welche Rolle soll das Unendliche in der Mathematik spielen? Welche Eigenschaften haben die verschiedenen Axiomensysteme? Schon in seiner 1929 bei Hans Hahn abgeschlossenen Dissertation behandelte Gödel eine dieser Grundlagenfragen: Ist die Prädikatenlogik erster Stufe vollständig? Seine positive Antwort war ein beachtenswertes Ergebnis der jungen mathematischen Logik. 1930 konnte Gödel aber ein bahnbrechendes mathematisches Resultat erzielen. Mathematische Systeme, die zumindest die natürlichen Zahlen umfassten, waren unvollständig. Gödels Unvollständigkeitssatz machte den jungen Mathematiker sofort berühmt. Gödel pendelte ab 1934 zwischen Wien und den USA und ging dann 1940 definitiv in die Vereinigten Staaten, wo er bis zu seinem Lebensende an dem Institute for Advanced Study in Princeton wirkte.

1931

In seinem Beweis der Unvollständigkeit zeigte Gödel, dass in mathematischen Systemen der Stärke der Arithmetik Sätze konstruiert werden können, die zwar gültig sind, die man aber nicht beweisen kann. Durch die Existenz solcher unbeweisbarer Sätze ist die Mathematik unvollständig. Zwei zentrale Forderungen des Programms des deutschen Mathematikers David Hilbert waren somit nicht erfüllbar: der Beweis der Vollständigkeit und der Widerspruchsfreiheit für die Arithmetik und stärkere Systeme.

Ein dritter Punkt des Programms war aber noch offen: das Entscheidungsproblem. Auch wenn manche Sätze nicht beweisbar sind, stellt sich die Frage, ob es ein allgemeines, formales Verfahren gibt, um festzustellen, welche mathematischen Sätze beweisbar und welche nicht beweisbar sind.
Die Antwort auf diese Frage wurde zur Grundlage der theoretischen Informatik. Unter dem prägenden Einfluss von Gödel wurde das Problem schließlich von dem amerikanischen Mathematiker Alonzo Church und dem britischen Mathematiker Alan Turing gelöst: Es gibt kein solches Verfahren. Um die Frage zu beantworten, musste man definieren, was ein Algorithmus und was Berechenbarkeit ist, zwei Grundbegriffe der modernen Informatik.

Der Wert und die Wirkung seiner Theorie

Wohl keine Erfindung im 20. Jahrhundert hat den Alltag der Menschen so stark verändert wie der Computer. Die Bedeutung von Gödels rein mathematischem Ergebnis wurde sofort von John von Neumann erkannt und beeinflusste Alan Turing. In Folge des Unvollständigkeitsbeweises versuchten Gödel, Church und
Turing zu definieren, was Berechenbarkeit bedeutet. Die Turing-Maschine ist eine solche Definition der Berechenbarkeit, sie ist zugleich der theoretische Entwurf eines Computers. Durch Gödels und Turings Arbeit wurde die Mechanisierung komplexer Denkprozesse möglich.

Turing und von Neumann legten dann in den 1940er Jahren die Grundlage für den modernen Computer. 1960 gab es in den Vereinigten Staaten schon 6000 Computer und heute weltweit über eine Milliarde. Allein 2015 wurden 215 Millionen Computer verkauft. Die Firma Google hat an die 900.000 Computer in ihren Server-Farmen. 42% der Weltbevölkerung benützen das Internet, den weltweiten Verbund von Rechnernetzwerken.

„Kurt Gödels bahnbrechende Resultate über die Unvollständigkeit axiomatischer Systeme haben die zentralen Begriffe der Mathematik und der Informatik, die Beweisbarkeit und die Berechenbarkeit, überraschend und dramatisch geklärt.“
_{Sy David Friedman, Professor für mathematische Logik an der Universität Wien}