Andere unentscheidbare Probleme ::: Theoretische Informatik

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

Halteproblem Entscheidbarkeit Nichtdeterminismus (Ergänzung)

Ψ Die Informatikseite

Andere unentscheidbare Probleme

Satz von Rice

Fußnoten