Königsberger Brückenproblem

Das Halteproblem

Letztmalig dran rumgefummelt: 22.11.07 08:55:54

Das Halteproblem ist eines der wichtigsten Entscheidungsprobleme (Entscheidbarkeit) Es fragt nach einem Algorithmus, mit dem man bei Programmen, Automaten oder Computern feststellen kann, ob sie für gewisse oder für alle Eingaben anhalten oder nicht.

1. Problembeschreibung
2. Hintergründe und Zusammenhänge - Einordnung in Klassen
3. Lösungsalgorithmen
4. Programmvorschläge
5. Zusammenfassung
6. Weiterführende Literatur
7. Linkliste zum Thema

Beachte vor allem bei Problemlösungsalgorithmen: Murphys Gesetze sowie deren Optimierung durch Computer sowie deren Optimierung durch Computer

1. Problembeschreibung

Sei K eine Klasse von Automaten. Das Halteproblem für K ist die Frage nach einem Algorithmus, mit dem man für jeden beliebigen Automaten A aus K und jedes Eingabewort x entscheiden kann, ob A bei der Abarbeitung von x nach endlich vielen Schritten stoppen wird oder nicht. Von besonderem Interesse ist die Klasse der Turingmaschinen:
Das Halteproblem für Turingmaschinen ist nicht entscheidbar, d. h., es gibt keinen Algorithmus, der für alle Turingmaschinen und für alle möglichen Eingaben entscheidet ob die Turingmaschine mit dieser Eingabe anhält oder nicht. Dieser Satz schließt nicht aus, dass man für spezielle Turingmaschinen entscheiden kann, ob sie halten. Er besagt lediglich, dass es kein allgemeines Verfahren für alle Turingmaschinen gibt. Das Halteproblem bleibt unentscheidbar, wenn man die Eingabe fest vorgibt, z. B. stets das leere Wort. Die Unentscheidbarkeit des Halteproblems beweist man mit Hilfe eines Widerspruchs, den man durch Diagonalisierung erzeugt.
Da Programme und Turingmaschinen im wesentlichen das gleiche leisten (Churchsche These), folgt aus diesem Satz:
Es gibt kein automatisches Verfahren, mit dem man für jedes Programm entscheiden kann, ob es eine Endlosschleife enthält oder nicht. Diese Tatsache ist für die Informatik sehr gravierend. Sie besagt gleichzeitig, dass man die Korrektheit (Semantik, Verifikation) eines Programms, also die Eigenschaft, auf Eingabewerte immer mit den gewünschten Ausgabewerten zu antworten, nicht automatisch überprüfen kann. Um die Korrektheit eines Programms zu beweisen, wird daher immer eine gewisse "Handarbeit'-und Intuition im Einzelfall nötig sein.
Weitere unentscheidbare Probleme, die man auf das Halteproblem zurückführt, sind z. H das allgemeine Wortproblem, das Leerheitsproblem und das Post'sche Korrespondenzproblem.

Die McCarthy-Funktion

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

effiziente Lösung nur als rekursiver Algorithmus
gegenseitige Rekursion - die Funktionen für größer 100 und kleiner 100 für die Zwischenwerte rufen sich gegenseitig auf

3. Lösungsalgorithmus

4. Programmvorschläge

5. Zusammenfassung

6. Weiterführende Literatur

der Lösungsalgorithmus der Türme von Hanoi ist nicht komplex, jedoch schon mit geringer Anzahl n mächtig
es muss also insgesamt hoher Lösungsaufwand betrieben werden - auch ein Computer wird für n=1000 in absehbarer Zeit keine Lösung bringen

7. Links zum Thema

zur Hauptseite

... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehmen ;-)

„Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“

Diddi Hallervorden, dt. Komiker und Kabarettist

Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-)

	Das Halteproblem ist eines der wichtigsten Entscheidungsprobleme (Entscheidbarkeit) Es fragt nach einem Algorithmus, mit dem man bei Programmen, Automaten oder Computern feststellen kann, ob sie für gewisse oder für alle Eingaben anhalten oder nicht.
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema



	Beachte vor allem bei Problemlösungsalgorithmen: Murphys Gesetze sowie deren Optimierung durch Computer sowie deren Optimierung durch Computer

	Sei K eine Klasse von Automaten. Das Halteproblem für K ist die Frage nach einem Algorithmus, mit dem man für jeden beliebigen Automaten A aus K und jedes Eingabewort x entscheiden kann, ob A bei der Abarbeitung von x nach endlich vielen Schritten stoppen wird oder nicht. Von besonderem Interesse ist die Klasse der Turingmaschinen: Das Halteproblem für Turingmaschinen ist nicht entscheidbar, d. h., es gibt keinen Algorithmus, der für alle Turingmaschinen und für alle möglichen Eingaben entscheidet ob die Turingmaschine mit dieser Eingabe anhält oder nicht. Dieser Satz schließt nicht aus, dass man für spezielle Turingmaschinen entscheiden kann, ob sie halten. Er besagt lediglich, dass es kein allgemeines Verfahren für alle Turingmaschinen gibt. Das Halteproblem bleibt unentscheidbar, wenn man die Eingabe fest vorgibt, z. B. stets das leere Wort. Die Unentscheidbarkeit des Halteproblems beweist man mit Hilfe eines Widerspruchs, den man durch Diagonalisierung erzeugt. Da Programme und Turingmaschinen im wesentlichen das gleiche leisten (Churchsche These), folgt aus diesem Satz: Es gibt kein automatisches Verfahren, mit dem man für jedes Programm entscheiden kann, ob es eine Endlosschleife enthält oder nicht. Diese Tatsache ist für die Informatik sehr gravierend. Sie besagt gleichzeitig, dass man die Korrektheit (Semantik, Verifikation) eines Programms, also die Eigenschaft, auf Eingabewerte immer mit den gewünschten Ausgabewerten zu antworten, nicht automatisch überprüfen kann. Um die Korrektheit eines Programms zu beweisen, wird daher immer eine gewisse "Handarbeit'-und Intuition im Einzelfall nötig sein. Weitere unentscheidbare Probleme, die man auf das Halteproblem zurückführt, sind z. H das allgemeine Wortproblem, das Leerheitsproblem und das Post'sche Korrespondenzproblem.
	*Die McCarthy-Funktion*


	effiziente Lösung nur als rekursiver Algorithmus
	gegenseitige Rekursion - die Funktionen für größer 100 und kleiner 100 für die Zwischenwerte rufen sich gegenseitig auf


	der Lösungsalgorithmus der Türme von Hanoi ist nicht komplex, jedoch schon mit geringer Anzahl n mächtig
	es muss also insgesamt hoher Lösungsaufwand betrieben werden - auch ein Computer wird für n=1000 in absehbarer Zeit keine Lösung bringen