+3 Daumen
144 Aufrufe
Hallo, ich verstehe nicht, wie ich folgendes zeigen / entscheiden soll:

Ist folgende Sprache entscheidbar / semi-entscheidbar?
L={ <M> | ∃w € ∑* so dass M bei w hält}

Ich habe verstanden, dass akzeptieren bedeutet, dass M auf gültige w hält (und JA ausgibt) auf ungültige w (also w nicht in L) nicht halten muss: Semi-Entscheidbar.
Und dass "Entscheidbar" meint, dass M auch auf ungültige w (s.o.) hält und ein (NEIN) ausgibt.

Auch, dass ich diese definition auf "Aufzählbarkeit" von L und L' (inverses) zurückführen kann. Ist L oder L' aufzählbar, dann ist L semi-entscheidbar. Sind L und L' aufzählbar so ist L entscheidbar.

Da ich hier aber jetzt L über eine "Codierte" Turingmaschine definiere, kann L doch gar nicht entscheidbar bzw semi-entscheidbar sein, da M laut Definition nicht für alle w halten muss. Hält M nicht immer und schon gar nicht zwingend bei einem JA kann ich über die Codierte TM gar nichts sagen?

Kann mir jemand helfen?
von
L={ <M> | ∃w € ∑* so dass M bei w hält}


Sorry irgendwie wurde das <M> als HTML erkannt.
Wenn ich mich daran noch richtig erinnere, musst du es in der Regel auf das Halteproblem von Turingmaschinen zurück führen.

Google das mal...

Bitte logge dich ein oder registriere dich, um die Frage zu beantworten.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...