Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Wieso ist L nicht entscheidbar?

–1 Punkt
30 Aufrufe

Hallo,

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

Danke!

 

Gefragt 25, Sep 2015 in 2011-H-05 von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

0 Punkte
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)
Beantwortet 25, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
> 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
...