Beweisarchiv: Theoretische Informatik: Berechenbarkeit: Halteproblem

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.

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

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.

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!