| Die letzten 2 Beiträge |
| 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 |
| 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 |
|
|
