| Die letzten 3 Beiträge |
| Mira94 |
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. :/ |
| ed209 |
Hi
kannst du mit eigenen Worten wiedergeben:
1. Wie E definiert ist?
2. Wie Q definiert ist?
3. Was Du beweisen sollst?
Gruß,
ED |
| Mira94 |
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 |
|
|
