INFORMATIKaufgabe "Halteproblem"

[uniaccount]

..also ich hab da so ne aufgabe.. hab aber keine ahung wär nett, wenn mir das jemand ausführlich erklären könnte


Was ist falsch an dem folgenden Szenario:
In einer isolierten Gesellschaft besitzt jeder/jede sein/ihr eigenes Haus. Der Maler dieser Gesellschaft behauptet, dass er genau die Häuser anmalt, die nicht von ihren Besitzern angemalt werden.
Was hat dieses Szenario mit dem Halteproblem zu tun?

PS: es geht um Javaprogrammierung und so zeugs.

[Steffen M.]

..also ich hab da so ne aufgabe.. hab aber keine ahung wär nett, wenn mir das jemand ausführlich erklären könnte

Also zunächst einmal gehe ich davon aus, dass Du Informatik studierst und diese Fragen Dich im Rahmen einer Vorlesung zur Theoretischen Informatik tangieren. Ich hatte mich selbst damit beschäftigt, das ist aber schon einige Semester her.

Was ist falsch an dem folgenden Szenario:
In einer isolierten Gesellschaft besitzt jeder/jede sein/ihr eigenes Haus. Der Maler dieser Gesellschaft behauptet, dass er genau die Häuser anmalt, die nicht von ihren Besitzern angemalt werden.

Ich kannte das bisher nur mit dem Barbier, der alle rasiert nur nicht die, die sich selbst rasieren. Aber egal, das läuft aufs absolut Gleiche raus.

Soweit ist erst einmal nichts falsch an dieser Feststellung. Wenn man aber nun nachfragt, ob denn das Haus dieses Malers bemalt ist, hat man ein Problem, und zwar ein ganz gewaltiges:

• Denn nimmt man einmal an, er bemale auch sein eigenes Haus, dann würde ja daraus folgern, dass er es nicht tut (denn er bemalt ja nur Häuser von Leuten, die nicht selbst malen).
  
  
• Nimmt man jedoch das Gegenteil an, nämlich, dass er sein eigenes Haus nicht bemalt, dann würde ja daraus folgern, dass er es eben doch bemalt. Denn er bemalt ja alle Häuser, die nicht von ihrem Besitzer selbst bemalt werden.

Ein klassisches Paradoxon.

Ganz ähnlich ist das "Halteproblem" in der Informatik. Vereinfacht gesagt, kann man jeden Rechner und jede Software abstrakt in Form einer sogenannten "Turingmaschine" modellieren. Jeder Rechner ist, wenn man so will, eine Approximation einer Turingmaschine. Diese besteht aus einem unendlich langen Band (man wählt es unendlich lang, um sich keine unnötigen Speichergrenzen zu schaffen, wenn es nur darum geht, zu entscheiden, ob ein Problem überhaupt berechenbar ist oder nicht) und einem Schreib-/Lesekopf, den man sich ähnlich zu einem Tonbandgerät vorstellen kann. Weiterhin gibt es eine elektronische Schaltung ("Logik"), die sich verschiedene Zustände merken kann und vom Konstrukteur der Maschine Regeln vorgegeben bekommt, die besagen, was sie tun soll, wenn sie sich in einem bestimmten Zustand befindet und auf der aktuellen Bandposition ein bestimmtes Zeichen liest.

Diese elektronische Schaltung ist verbunden mit dem Bandlaufwerk und dem Schreib-/Lesekopf. Dieses Band kann von der Maschine nun mit Zeichen aus einem vorgegebenen Zeichenvorrat (Alphabet) beschrieben werden, ebenso kann die Maschine die Zeichen auf dem Band wieder lesen. Die Maschine kann Zustände wechseln, das Band nach links oder nach rechts bewegen oder anhalten. Anhalten macht am Ende einer Berechnung Sinn.

Daher kommt der Name "Halteproblem".

Nun baut natürlich niemand solche Maschinen mit Band. Diese existieren nur formal auf dem Blatt Papier. Man kann aber alles, was man mit einem Rechner machen kann, auch mit einer solchen Turingmaschine berechnen (vgl. "Church'sche These"). Daher können wir das Halteproblem auch auf "Java-Programme" übertragen. Ein Java-Programm kann anhalten (fertig sein, beenden) oder aber in eine Endlosschleife geraten, die zu keinem Ergebnis führt (festhängen, abstürzen).

Das "Halteproblem" ist also nun die Frage: Hält ein vorgegebenes Java-Programm, gefüttert mit einer vorgegebenen Eingabe an oder hält es nicht an, d.h. gerät es in eine Endlosschleife? Das ist ein klassisches Entscheidungsproblem.

Es wurde von Logikern aber bewiesen, dass dieses Problem unentscheidbar ist, man kann also keine Maschine bauen, der man ein Java-Programm inkl. Benutzereingabe "verfüttert" und dann von ihr ausgegeben bekommt: "Dein Java-Programm AB wird bei der Eingabe XY sicher anhalten" oder "Dein Java-Programm AB wird bei der Eingabe XY nicht anhalten". Eine solche Maschine kann es nicht geben. Warum?

Dann tun wir mal so, als gäbe es sie doch. Sagen wir, ein ganz genialer Erfinder habe eine Turingmaschine (oder einen Computer mit einer genialen Software) konstruiert, die es doch entscheiden könne. Nennen wir diese Maschine "Haltetest". Diese Maschine bekomme als Eingabe:

• Ein beliebiges Java-Programm (z.B. den Quellcode)
  
• Die Eingaben, die der Benutzer dem Programm evtl. mitgibt

Als Ausgabe liefere sie:

• Programm hält, falls das übergebene Java-Programm bei der mitgegebenen Benutzereingabe anhält - oder andernfalls
• Programm hält nicht.

Sagen wir, wir hätten diesem genialen Erfinder eine solche Haltetest-Maschine (oder ein solches Programm - wie man's halt nimmt) abgekauft. Wir nehmen nun diese Maschine her, und setzen sie in eine von uns gebaute, größere Maschine hinein.

Diese "größere Maschine" soll folgendes machen:

• Sie kennt ihren eigenen Quellcode - das ist ja kein Problem.
  
  
• Sie ruft die vom Erfinder erworbene Haltetest-Routine (quasi als Unterprogramm) auf und übergibt dieser den eigenen Quellcode. Mit "eigenen" meine ich den Quellcode der größeren, äußeren, von uns konstruierten Maschine.
  
  
• Laut der Aussage des genialen Erfinders wird jetzt die von ihm konstruierte Haltetest-Maschine entweder mit "Hält" oder "Hält nicht" dem Aufrufer antworten. Der Aufrufer ist die äußere, größere Maschine.
  
  
• Angenommen, sie antwortet mit "Der übergebene Code (das ist der Code der äußere Maschine) hält", dann jagen wir die äußere Maschine in eine Endlosschleife (nach dem Schema: "while true {}").
  
  
• Angenommen, sie antwortet mit "Der übergebene Code hält nicht", dann beenden wir die äußere Maschine ordnungsgemäß. Wir halten also an.

Was ist passiert? Die äußere Maschine schafft es immer, die vom Erfinder erworbene Haltetest-Maschine auszutricksen. Wenn immer die Haltetest-Maschine sagt, dass die äußere Maschine anhält, dann hält die äußere Maschine eben nicht an. Und wenn immer die Haltetest-Maschine sagt, dass die äußere Maschine nicht anhält, dann lassen wir sie eben anhalten.

Mit anderen Worten: Es ist kein Problem, die Aussage der Haltetest-Maschine dazu zu verwenden, dann nachher doch das Gegenteil zu machen.

Oder, nochmals anders ausgedrückt: Wir haben einen Widerspruch konstruiert. Und da wir nichts logisch Falsches gemacht haben (denn selbstverständlich dürfen wir eine Maschine in eine andere einbetten), muss der Widerspruch in unserer Annahme (bzw. im Verkaufsversprechen des genialen Erfinders, der uns die Haltetest-Maschine verkauft hat) begründet sein. Demnach ist also die Behauptung, es gäbe eine Maschine, die entscheiden kann, ob eine beliebige Maschine (oder meinetwegen auch ein beliebiges Java-Programm) anhält oider nicht, widerlegt. Eine solche Maschine kann es nicht geben.

Dass es in der Praxis natürlich rechnergestützte Prover gibt und Mechanismen existieren, um mit Rechnerasisstenz Fehler in Software zu suchen, ist eine andere Sache. Diese Programme sind aber stets in ihrer Mächtigkeit begrenzt, und ein Tester, der Software allgemein auf Fehlerfreiheit checken kann, kann nicht existieren. Daher ist, und das ist jetzt meine Interpretation, die Aussage, dass eine Software X irgendwann einmal garantiert fehlerfrei sein wird, genauso Unfug.

Wir haben gesehen: Das Halteproblem ist also nicht entscheidbar. Es ist aber immerhin noch semi-entscheidbar. (Es gibt auch Probleme, die nicht einmal mehr semi-entscheidbar sind). Genaueres hierzu bei Bedarf, denn da müsste man wohl noch weiter ausholen.

Was hat dieses Szenario mit dem Halteproblem zu tun?

Wie Du siehst, führt sowohl die Annahme, dass ein solcher Maler existiert als auch die Annahme, dass "Haltetest" existiert, zu einem logischen Widerspruch. Im Prinzip ist es genau das selbe. Das Maler-/Barbierproblem einerseits und das Halteproblem andererseits versagen immer dann, wenn das Haus des Malers, der Bart des Barbiers oder Haltetest mit sich selbst konfrontiert werden.

Im Prinzip beruht das auf den Widerspruch, den Russel an der Cantor'schen Mengenlehre fand, und zwar mit der Aussage: "Sei M die Menge aller Mengen, die sich nicht selbst enthalten" und der damit verbundenen Frage: "Enthält M sich selbst?". Viel Spaß beim Grübeln! ;-)

PS: es geht um Javaprogrammierung und so zeugs.

Naja, so grob jedenfalls. Sagen wir so, es geht um Logik, und ein Javaprogramm kann ein Beispiel dafür sein. Genauso hätten wir das jetzt auch mit C-, Pascal-, Basic-, Brainf**k-, Whitespace-, usw... -Programmen machen können. Es ist nicht programmiersprachengebunden, Endlosschleifen oder nicht endende Berechnungen kann ich in "turingmächtigen" Programmiersprachen immer erzeugen und Fehler kann es immer geben.

Ich hoffe, dass das halbwegs klar wurde. Ich habe bewusst auf Formalien verzichtet.

Gruß,
Steffen