0 Daumen
60 Aufrufe

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

von

Was ist Tw(xm)?

1 Antwort

0 Daumen

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.

von 4,5 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community