semi-entscheidbarkeit |
01.06.2013, 09:10 | Auf diesen Beitrag antworten » |
bradig | semi-entscheidbarkeit ich möchte zeigen ,dass weder das äquivalenzproblem EQ für DTM semi-entscheidbar ist noch das Komplement von EQ. EQ={<code(A),code(B)>/ A1 und A2 ist DTM und L(A1)=L(A2)}. ich sollte dazu die Reduktion und komplement des Haltproblems verwenden. Meine Beweisideen: ich zeige dass , 1)Komplement(HP)<= Komplement(EQ) ist 2)Komplement (HP)<=EQ ist und daraus folgt ,dass weder EQ noch Komplement(EQ) semi-entscheidbar ist. Bitte Hilfe beim umsetzen,da ich nicht weiß wie ich das ganze beweisen kann. ich weiß, dass HP semi entscheidbar ist und dass Komplement(HP) ist es auch. herzlich ps:<= bedeutet kleiner gleich |
|
|
01.06.2013, 12:05 | Auf diesen Beitrag antworten » |
Karlito | Hallo, leider stecke ich in dem Thema nicht mehr so gut drin. D.h. es kann sein, dass ich dich nicht beraten kann. Versuchen wir es trotzdem: Als erstes: das komplement des Halteproblems ist nicht semientscheidbar! Zweitens: wie sähe denn eine Reduktion auf das Halteproblem oder dessen Komplement aus? (Sorry, wenn ich die Richtung verwechsle). Wie könnte uns das weiterhelfen? VG, Karlito |
|