German in science #2: Entscheidungsproblem

»loan words« aus dem Deutschen in der englischen Wissenschaftssprache.

Goerge Dysons gut informiertes, umfangreiches Buch Turings Kathedrale über die frühen Jahre der Computerentwicklung streift natürlich auch die theoretische Informatik. Und in diesem Zusammenhang taucht bei Turing die Verwendung des Begriffs Entscheidungsproblem auf. Anlass genug, nicht nur diesen weltweiten Export eines dt. Fachbegriffes zu würdigen, sondern auch mal kurz auf die Thematik zu blicken. Man möge mir als Nicht-Mathematiker die gewisse Oberflächlichkeit im Folgenden nachsehen:

Das Entscheidungsproblem wurde schon 1900 von David Hilbert formuliert:
„Gibt es ein Verfahren, das für jede ausreichend formalisierte Aussage der Mathematik entscheidet, ob diese wahr oder falsch ist?“

Anders formuliert lautete die Kernfrage der Logiker und Mathematiker zum Entscheidungsproblem: Gibt es einen Algorithmus der von einer beliebigen Formel eines logischen Kalküls feststellt, ob sie aus gewissen vorgegebenen Axiomen folgt oder nicht?“

Erst im Jahr 1936 konnte u.a. Alan Turing beweisen, dass obiges Entscheidungsproblem nicht lösbar ist:

In seinem Aufsatz On Computable Numbers, with an Application to the “Entscheidungsproblem” führte der Brite Alan Turing (1912–1954) universelle Berechnungsmodelle (Codes) und Universalmaschinen (die sog. Turing-Maschinen) ein und ersetzte somit die bis dahin eher arithmetisch-basierte formale Sprache z.B. eines Kurt Gödel.

Die Arbeitsweise der Turingmaschine ist vergleichbar mit der eines Menschen oder einer Maschine, wenn sie Symbole auf einem Blatt Papier oder in einem elektronischen Speicher ändern. In jedem Schritt wird ein Zeichen durch ein vorgegebenes Programm gelesen und überschrieben. Danach rückt es eine Speicherzelle weiter oder hält an.
Bis heute ist kein berechenbares Problem bekannt, das nicht bereits mit der Turingmaschine lösbar wäre.
Turing begründete mit dieser Arbeit einen neuen Zweig der Mathematik

Beispiel: Halteproblem
Das Halteproblem beschreibt die Frage, ob ein Algorithmus mit einer Eingabe terminiert (abstürzt).
Ein leider alltägliche Situation steht genau für dieses Problem: Man sitzt vor dem PC-Monitor und fragt sich: "Ist der Computer abgestürzt oder rechnet er noch?"
Verallgemeinert: Zu einem beliebigen Programm und einem Satz von Eingabedaten soll entschieden werden, ob dieses Programm mit diesen Daten nach endlicher Zeit stoppt oder nicht.

Alan Turing wies die Unentscheidbarkeit dieser Frage nach, d.h. er bewies, dass es kein Programm gibt, welches diese Frage beantwortet.

In seiner Antwort auf das Entscheidungsproblem führte Turing also den Nachweis, dass es kein systematisches Verfahren gibt, das es uns erlauben würde, durch das bloße Betrachten eines Codes vorauszusehen, was dieser Code tun wird.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.