Aufgabe:
Zeige unter Anwendung des Satzes von Rice, dass die folgende Sprache nicht entscheidbar ist. Begründe die Nicht-Trivialität der Menge S.
L2= {〈M〉∣ M ist eine deterministische Turingmaschine und | L(M) | ≤ 2. }
Hierbei ist L(M) die von der deterministischen Turingmaschine M akzeptierte Sprache.
Ansatz/Problem:
Die Sprache L2 könnte man vielleicht mit einer Sprache gleichsetzen { 〈M〉 | M berechnet höchstens von einer deterministischen Turingmaschine M akzeptierte Sprachen.}. Dann könnte man eine Funktion S aufführen:
S = { f: Σ* -> | L (M) ≤ 2 }. Die Funktion f gibt eine Sprache L (M) raus. M wird das Wort w aber nicht mehr als maximal 2 Mal durchlaufen. Die Nicht-Trivialität der Menge könnte man dadurch zeigen, dass S einen Wert zurückgibt, der nicht 0 ist. Nur wie das noch formell zeigen?
