 semi-entscheidbarkeit |
bradig
Grünschnabel
Dabei seit: 20.05.2013
Beiträge: 7
 |
|
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 09:10 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
01.06.2013 12:05 |
|
|
|
