Beweisarchiv: Theoretische Informatik: Berechenbarkeit: Halteproblem
Beweisarchiv: Theoretische Informatik
Das spezielle Halteproblem
BearbeitenBeschreibung
Bearbeiten< > | ist eine Turingmaschine, die bei Eingabe < > hält
Anmerkung
ist eine Kodierungsfunktion, die jeder Turingmaschine eine eindeutige Kodierung zuordnet. Und umgekehrt beschreibt jedes eine gültige Turingmaschine.
Behauptung
Bearbeitenist nicht entscheidbar.
Beweis
BearbeitenAngenommen sei entscheidbar, sagen wir durch eine Turingmaschine (TM) . Dann lässt sich zu einer gegebenen TM eine TM konstruieren, die (bei Eingabe < >) genau dann hält, wenn nicht hält. Konstruktion der Maschine : Zu einer gegebenen Maschine entscheidet man zunächst mittels ob (bei Eingabe < >) hält. Falls dem so ist, gehe in eine Endlosschleife. Andernfalls halte.
Formal also:
Angenommen löse das spezielle Halteproblem.
Definiere für Eingabe < > als (mit Eingabe x mit Eingabe < >) Endlosschleife terminiere
Oder in Pseudocode:
Es gilt für alle also: mit Eingabe < > hält (mit Eingabe < >) hält nicht (*)
Aus Anwendung von mit < > gilt (vgl. (*)):
(mit Eingabe < >) hält (mit Eingabe < >) hält nicht.
Widerspruch!
Das allgemeine Halteproblem
BearbeitenBeschreibung
Bearbeiten< ># | hält bei Eingabe
Behauptung
BearbeitenH ist unentscheidbar
Beweis
BearbeitenAngenommen, H sei entscheidbar, dann wäre auch K entscheidbar. Widerspruch!
Das Halteproblem bei leerem Wort
BearbeitenBeschreibung
Bearbeiten< > | ist eine TM, die beim leerem Wort als Eingabe hält
Behauptung
Bearbeitenist unentscheidbar.
Beweis
BearbeitenAngenommen, sei entscheidbar. Sagen wir durch eine TM . Wir erzeugen einen Widerspruch, indem wir zeigen, dass dann entscheidbar wäre. Sei also < ># eine Probleminstanz von . Wir erzeugen eine Maschine die sich bei leerer Eingabe genau so verhält, wie bei Eingabe . Konstruktion von : schreibt zunächst auf das Band und simuliert dann die TM . Setzt man nun auf so gilt:
mit leerer Eingabe hält hält mit Eingabe
bzw. mengentheoretisch
< > < >#
Da die Konstruktion von aus von einer TM übernommen werden kann, ist damit entscheidbar. Widerspruch!