Reduktionen und Entscheidbarkeit |
| 20.01.2014, 20:24 | Auf diesen Beitrag antworten » |
| liofly | Reduktionen und Entscheidbarkeit Hallo ich habe Probleme bei folgender Aufgabe: Gegeben sind die folgende Sprachen (<M> bezeichnet eine geeignete Kodierung der Turingmaschine M):
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! |
|
|
|
|
|