semi-entscheidbarkeit

Neue Frage »

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
 
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
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »