Unterabschnitte
Sei S eine nichtleere, echte Teilmenge der Menge aller partiellen berechenbaren Funktionen
. Dann ist die Sprache
unentscheidbar.
Beweis: Wir beweisen dies, indem wir zeigen:
Kleine Vorbemerkung: 
ist das Problem, ob eine Turingmaschine bei leerem Wort anhält. Dies is also ein Spezialfall des Halteproblems.

ist das Komplementproblem. Alle Codewörter

, bei der die Turingmaschine

bei der Eingabe
nicht anhält, sind in der Sprache enthalten.
Jetzt geht's los: Wir führen nur den Fall aus, daß

.

ist die Funktion, die überall undefiniert ist.
1.
:
Wir wählen eine beliebige Funktion

, die nicht in

liegt.
Wir definieren eine Funktion

folgendermaßen:
Um die Funktion

zu berechnen, simulieren wir zuerst

. Wenn

anhält, dann kann es erst weitergehen. Das Problem aber, ob

anhält ist alleine schon unentscheidbar (das beweisen wir erst weiter unten
18), deshalb ist die ganze Geschichte unentscheidbar.
2.
:
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

mit der Eingabe

wird so

mit der Eingabe

für das Halteproblem mit leerem Wort.
Fußnoten
- ... unten18
- Halteproblem