Spezielles Halteproblem

Gegeben sei die Selbstanwendbarkeitsmenge

Die Menge ist nicht entscheidbar.

Beispiel

• Annahme: Es gibt eine Maschine, die feststellen kann ob ein beliebiges Programm hält. Wir nennen die Maschine jetzt mal T2000
• Wir können der Maschine jetzt sagen, sie soll halten, wenn das Programm nicht hält, und nicht halten, wenn hält. - Jetzt lassen wir den T2000 einmal sich selbst analysieren. Daraus würde folgen:
  • T2000 hält T2000 hält nicht
  • T2000 hält nicht T2000 hält
• Widerspruch, Annahme ist falsch!