Beweisarchiv: Theoretische Informatik: Berechenbarkeit: Halteproblem
Beweisarchiv: Theoretische Informatik
Das spezielle Halteproblem Bearbeiten
Beschreibung 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 Bearbeiten
ist nicht entscheidbar.
Beweis Bearbeiten
Angenommen 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 Bearbeiten
Beschreibung Bearbeiten
< ># | hält bei Eingabe
Behauptung Bearbeiten
H ist unentscheidbar
Beweis Bearbeiten
Angenommen, H sei entscheidbar, dann wäre auch K entscheidbar. Widerspruch!
Das Halteproblem bei leerem Wort Bearbeiten
Beschreibung Bearbeiten
< > | ist eine TM, die beim leerem Wort als Eingabe hält
Behauptung Bearbeiten
ist unentscheidbar.
Beweis Bearbeiten
Angenommen, 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!