---

Geschrieben von Mira94 am 29.10.2014 um 18:42:

  Reduktion und Entscheidbarkeit

Hallo, ich habe eine Aufgabe, wo folgendes gegeben ist:
Die Sprachen ((M) bezeichnet eine geeignete Kodierung der TM M über dem Alphabet Sigma.
E={(M)|L(M) = leere Menge}
Q={(M1),(M2)|L(M1)=L(M2)}
Zeigen Sie die folgende Aussage:
E<gleich Q.
Kann mir jemand sagen, wie ich das zeigen kann. Ich habe da nämliche überhaupt keine Ahnung. Bin auch relativ neu im Gebiet der TM.
Danke im Voraus
Mira94

---

Geschrieben von ed209 am 29.10.2014 um 19:43:

 

Hi

kannst du mit eigenen Worten wiedergeben:
1. Wie E definiert ist?
2. Wie Q definiert ist?
3. Was Du beweisen sollst?

Gruß,
ED

---

Geschrieben von Mira94 am 29.10.2014 um 20:04:

 

Also E<gleich Q bedeutet ja, E auf Q reduzierbar ist (laut Definition). Dies ist dann der Fall, wenn x element E <-> f(x) element Q ist bzw. x element E -> f(x) element Q und x kein Element von Q -> f(x) kein Element von Q.
Mehr weiß ich leider nicht. :/