Reduktion und Entscheidbarkeit |
| 29.10.2014, 18:42 | Auf diesen Beitrag antworten » |
| 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 |
|
|
|
| 29.10.2014, 19:43 | Auf diesen Beitrag antworten » |
| 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 |
| 29.10.2014, 20:04 | Auf diesen Beitrag antworten » |
| 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. :/ |
|
|
