---

Geschrieben von bradig am 01.06.2013 um 09:10:

  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

---

Geschrieben von Karlito am 01.06.2013 um 12:05:

 

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