Wieso ist L nicht entscheidbar?

Question

Hallo,

Wieso ist L semientscheidbar sondern nicht entscheidbar? Was ist der Unterschied?

Danke!

 

Answer 1

Semientscheidbar heißt, dass es einen Algorithmus/ein TM gibt, der irgendwann (in endlicher Zeit) terminiert, wennn die Antwort "JA" ist. Wenn die Antwort "Nein" ist, dann muss der Algorithmus/die TM nicht terminieren (siehe dazu auch das Erfüllbarkeitsproblem der Prädikatenlogik in Info I). Nichtentscheidbaren Probleme sind alle anderen Probleme, die nicht semi-entscheidbar sind. Entschiedbar ist ein Problem, wenn es einen Algorithmus gibt, der immer mit der richtigen Antwort nach endlicher Zeit terminiert.

Welches L meinst du/welchen Aufgabenteil? Kannst du zusätzlich bitte durch Schreibweise zwischen nichtentscheidbar (d.h. auch nicht semi-entscheidbar und nicht entscheidbar (Problem nicht in der Menge der entscheidbaren Probleme) unterscheiden? Sonst kann ich nicht eindeutig erkennen, was du meinst.

Tobias (Tutor)

Comments

> Nichtentscheidbaren Probleme sind alle anderen Probleme, die nicht semi-entscheidbar sind.

Das stimmt nicht! Semi-entscheidbare Probleme können auch unentscheidbar bzw. nichtentscheidbar sein.

Viele Grüße

Lukas König und Friederike Pfeiffer-Bohnen