zeige, dass H^(m,n) semi-entscheidbar ist zum Beispiel durch Angabe eines Semi-Entscheidungsverfahren

Question

Frage:

Sei H^(m,n) = {w#x} ∈ {0,1,#}^* | Ǝm,n ≥ 1, n≠m, so dass Tw(x^m) und Tw(x^n) halten}

a) zeige, dass H^(m,n) semi-entscheidbar ist zum Beispiel durch Angabe eines Semi-Entscheidungsverfahren

b) Zeigen Sie, dass H^(m,n) unentscheidbar ist, indem Sie einesder drei folgenden Probleme zur Reduktion auswählen:

(allgemeines Halteproblem ). H'(spezielles Halteproblem). Hε (HAlteproblem mit leerem Band).

Ich komme leider bei der Aufgabe gar nicht wie kann ein Problem unentscheidbar und Semi-entscheidbar gleichzeitig sein ich habe viele Entscheibarkeitsprobleme gelöst und verstanden aber leider komme ich hier gar nicht weiter ich bedanke mich fr jede Hilfe im Voraus

Comments

Was ist Tw(x^m)?

Answer 1

Semi-entscheidbar heißt eine Sprache, wenn es eine Turingmaschine gibt, die auf den Wörtern der Sprache akzeptierend hält und auf Wörtern, die nicht zu der Sprache gehören entweder nicht hält, oder verwerfend hält.

Entscheidbar heißt eine Sprache, wenn es eine Turingmaschine gibt, die auf den Wörtern der Sprache akzeptierend hält und auf Wörtern, die nicht zu der Sprache gehören verwerfend hält.

Unentscheidbar heißt eine Sprache, die nicht entscheidbar ist.