Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSamstag, 19. April 2014 

Halteproblem


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Das Halteproblem ist das grundlegende Beispiel für ein unentscheidbares Problem in der Theoretischen Informatik . Es beschäftigt sich mit der Frage eine in einer geeigneten Kodierung gegebene Turingmaschine auf einer gegebenen Eingabe anhält d.h. sie nicht unendlich lange läuft. Man kann der Turingmaschine auch ein Programm in einer üblichen Programmiersprache betrachten dies ein im wesentlichen äquivalentes Problem.

Die wichtigste Fragestellung bezüglich des Halteproblems nun ob es entscheidbar ist d.h. ob eine Turingmaschine existiert für jedes Paar aus kodierter Turingmaschine und berechnen kann ob die kodierte Maschine auf Eingabe anhält. In der angewandten Informatik lautet Frage: Kann man ein Programm entwickeln das als Eingabe den Quelltext eines zweiten Programms sowie dessen Eingabewerte welches entscheiden kann ob das zweite Programm d.h. nicht endlos weiterläuft.

Alan Turing bewies 1936 dass es keinen Algorithmus geben kann das Halteproblem für alle Eingaben löst.

Inhaltsverzeichnis

Beweis

Durch einen Widerspruchsbeweis lässt sich eindeutig zeigen dass eine Turingmaschine nicht existiert .

Angenommen es gibt eine Methode haltetest (Programmcode in Jana ):

boolean haltetest(↓char[] p ↓char[] e)
// Liefert true wenn das durch die Zeichenkette p dargestellte Programm bei den durch die e dargestellten Eingabedaten terminiert.

sowie eine zu testende Methode programm die innerhalb von haltetest aufgerufen werden muss:

programm(↓char[] e) {
// e ... Eingabedaten als Zeichenkette
 while (haltetest(e e)) {} } 

Wenn man nun der Methode programm (abgekürzt p ) sich selbst als Eingabedaten übergibt und von der Methode haltetest auf Terminierung prüfen lässt kann diese richtiges Ergebnis liefern:

  • liefert haltetest(p p) TRUE so hieße dies dass programm(p p) terminiert -- aber die Bedingung haltetest(p p) innerhalb von programm ist gerade dann immer wahr also wird die while-Schleife niemals beendet und damit kann programm(p p) nicht terminieren => Widerspruch!
  • liefert haltetest(p p) FALSE so müsste programm(p p) endlos weiterlaufen. Dann trifft aber die in der while-Schleife niemals zu und programm(p p) terminiert => ebenfalls Widerspruch!

Das heißt nun es gibt keine die erhält sie als Eingabe die Codierung Turingmaschine M und eine zugehörige Eingabe w Ja ausgibt wenn M auf w hält Nein ausgibt wenn M nicht auf w

Jedoch gibt es eine Turingmaschine die immer Ja ausgibt wenn M auf w hält aber endlos arbeitet wenn M nicht auf hält. Dies ist sogar trivial: natürlich kann geforderte Turingmaschine einfach warten bis M eventuell und dann Ja ausgeben.

Bereits ein Spezialfall des Halteproblems die ob eine Turingmaschine auf der leeren Eingabe genannt H0 ist nicht entscheidbar.

Konsequenzen

Mathematische Konsequenzen

Dieses zunächst unscheinbare Problem und seine hat weitreichende Konsequenzen:

Die mathematisch präzise formulierte Aufgabe des ist für eine Turingmaschine unlösbar. Setzt man die churchsche These als wahr voraus so können auch und letztlich Menschen das Halteproblem nicht lösen.

Das Halteproblem bedeutet für die Softwareentwicklung dass eine automatische Überprüfung von Programmlogik möglich ist.

Philosophisch-weltanschauliche Konsequenz

Geht man von der Existenz einer Gottheit aus und unterstellt man ihr sie allwissend und stehe nicht im Widerspruch zu Vorhandenen so hieße das dass sie prinzipiell das Halteproblem entscheiden können müsse. So muss Gottheit also die Fähigkeiten von Menschen und im Sinn von Berechenbarkeit übersteigen.

Geht man davon aus dass eine keiner Turingmaschine im oben angenommenen Sinn entspricht übersinnliche Fähigkeiten hätte so wäre ihre Nichtexistenz bewiesen.

Geht man aber davon aus dass Existenz einer Gottheit in Widerspruch zu Bekanntem also unlogisch ist weil niemand ein bewiesenermaßen Problem lösen kann so gäbe es keine Dies gilt insbesondere unter Voraussetzung der Vorstellung Gläubiger nach der Menschen deren mathematischen Fähigkeiten Halteproblem nicht zu lösen vermögen Ebenbilder einer sind. Dann könnte eine Gottheit nicht existieren! Nichtexistenz Gottes wäre bewiesen. Zumindest aber wäre dass eine Gottheit keine Maschine ist.

Diese philosophisch -weltanschauliche Konsequenz setzt allerdings die Korrektheit der churchschen These voraus.

Am Ende beweist diese These aber die Existenz noch die Nichtexistenz von Gott Gott wäre kein abzählbar potentiell unendlicher Automat die Turingmaschine.

Man muss beachten dass die Turingmaschine determiniert ist nur abzählbare Mengen bearbeitet und Zufall kennt. Sie ist eine theoretische Maschine. praktische Maschine hält zumindest wenn der Strom (allgemeiner wenn ein zufallsbedingter Zustand eintritt). Gott die Reset -Taste drücken. Die Frage ob dann die hält ist nicht entscheidbar.

Siehe auch



Bücher zum Thema Halteproblem

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Halteproblem.html">Halteproblem </a>