---

Geschrieben von liofly am 20.01.2014 um 20:24:

  Reduktionen und Entscheidbarkeit

Hallo ich habe Probleme bei folgender Aufgabe:

Gegeben sind die folgende Sprachen (<M> bezeichnet eine geeignete Kodierung der Turingmaschine M):

• E = {<M> | L(M) = 0}
  
• I = {<M> | |L(M)| = [Hier sollten das Zeichen für Unendlichkeit stehen)}
  
• Q = {(<M1>, <M2>) | L(M1) = L(M2)}
  

a) Welche der Sprachen sind entscheidbar; welche sind aufz¨ahlbar?
b) Zeigen Sie die folgenden Aussagen:
(i) E <= Q
(ii) I <= Q
(iii) Q <= I

Hier kann die Aufgabe nochmal als Screenshot etwas schöner formatiert gesehen werden (Ich darf leider keinen richtigen Link posten): root.weinprobe-in-den-weinbergen.de/pic/ReduktionUndEntscheidbarkeit.png

Mein Problem ist nun, dass ich nicht weiß wie ich anfangen soll das formal zu beweisen, bzw. ich habe überhaupt Probleme dabei zu verstehen was genau gefordert wird.

Ich wäre über jeden Tipp dankbar, den mir jemand geben kann.

Danke!