Reduzierbarkeit

Seien und Sprachen. Dann heißt auf reduzierbar (), wenn es eine totale berechenbare Abbildung gibt, sodass

Einfach gesagt

• Wir haben ein Wort einer Sprache , das hauen wir in eine Funktion, die das Wort in die Sprache übersetzt.
• Wörter von werden in Wörter von umgewandelt, Nichtwörter von werden in Nichtwörter von umgewandelt.
• Das funktioniert, weil “mehr kann” als , bzw. weil reduzierbar auf ist.
• WIr haben jetzt aus und der Funktion eine neue Maschine konstruiert, die genau die selben Wörter von entscheidet,
• Jetzt müssen wir uns nicht mehr anschauen sondern können uns nur noch um kümmern.

Wenn und entscheidbar ist ist entscheidbar.