0 Daumen
160 Aufrufe

Frage:

"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"

Code:Ansatz: 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? Oder ist das formeller Käse? Hat jemand eine Idee, wie man hier vorgehen könnte?

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community