Theoretische Informatik - Andere unentscheidbare Probleme

Nächste Seite: Nichtdeterminismus (Ergänzung) Aufwärts: Entscheidbarkeit Vorherige Seite: Halteproblem Inhalt

Unterabschnitte

Satz von Rice

Andere unentscheidbare Probleme

Satz von Rice

Sei S eine nichtleere, echte Teilmenge der Menge aller partiellen berechenbaren Funktionen $f:\{0,1\}^{*}\rightarrow \{0,1\}^{*}$ . Dann ist die Sprache

$\begin{displaymath}L_{S}=\{w\in\{0,1\}^{*}:\tau_{w}\,berechnet\,eine\,partielle\,Funktion\,f\in S\}\end{displaymath}$

unentscheidbar.

Beweis: Wir beweisen dies, indem wir zeigen:

$\begin{displaymath}\overline{H_{\epsilon}}\leq L_{S}\,und\,H\leq H_{\epsilon}\end{displaymath}$

Kleine Vorbemerkung: $H_{\epsilon}$ ist das Problem, ob eine Turingmaschine bei leerem Wort anhält. Dies is also ein Spezialfall des Halteproblems. $\overline{H_{\epsilon}}$ ist das Komplementproblem. Alle Codewörter $w=code(\tau_{w})$ , bei der die Turingmaschine $\tau_{w}$ bei der Eingabe $\epsilon$ nicht anhält, sind in der Sprache enthalten.
Jetzt geht's los: Wir führen nur den Fall aus, daß $f_{\bot}\in S$ .
$f_{\bot}$ ist die Funktion, die überall undefiniert ist.
1. $\overline{H_{\epsilon}}\leq L_{S}$ :
Wir wÃƒhlen eine beliebige Funktion $f_{f\not\in S}$ , die nicht in

liegt. Wir definieren eine Funktion $f_{w}$ folgendermaßen:

$\begin{displaymath}f_{w}=\left\{\begin{array}{ll}f_{\bot}&falls\,\tau_{w}\,bei\,... ...icht\,anh\uml {a}lt\\ f_{f\not\in S}&sonst\\ \end{array}\right.\end{displaymath}$

Um die Funktion $f_{w}$ zu berechnen, simulieren wir zuerst $\tau_{w}$ . Wenn $\tau_{w}$ anhält, dann kann es erst weitergehen. Das Problem aber, ob $\tau_{w}$ anhält ist alleine schon unentscheidbar (das beweisen wir erst weiter unten¹⁸), deshalb ist die ganze Geschichte unentscheidbar.
2. $H \leq H_{\epsilon}$ :
Um mit dem Halteproblem für das leere Wort das Halteproblem zu lösen, bauen wir einfach das Eingabewort für das normale Halteproblem schon in die Turingmaschine hinein. Dies können wir zum Beispiel tun, indem die Turingmaschine für das Halteproblem mit leerem Wort vorerst das Wort auf dem Band erst erzeugt. Aus $\tau_{x}$ mit der Eingabe

wird so $\tau_{x\char93 w}$ mit der Eingabe $\epsilon$ für das Halteproblem mit leerem Wort.

Fußnoten

... unten ¹⁸: Halteproblem

Nächste Seite: Nichtdeterminismus (Ergänzung) Aufwärts: Entscheidbarkeit Vorherige Seite: Halteproblem Inhalt