Zum Inhalt springen

Beweisarchiv: Theoretische Informatik: Berechenbarkeit: Halteproblem

Aus Wikibooks

Beweisarchiv: Theoretische Informatik

Sprachen: Pumping-Lemma
Berechenbarkeit: Halteproblem


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!