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.)

Schöne Ferien!
 

 

vorletzten Aussage: richtig, weil entscheidbar eine Teilmenge von semientscheidbar?

–1 Punkt
47 Aufrufe
Zur vorletzten Aussage (A ist semientscheidbar). A liegt doch in NP-vollständig und ist damit aufjedenfall entscheidbar.

Ist semi-entscheidbar deswegen richtig, weil entscheidbar eine Teilmenge von semientscheidbar ist?
Gefragt 26, Nov 2014 in BER-AH von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

0 Punkte
 
Beste Antwort

Hallo,

Genau. Nimm z.B. ein Wortproblem "$w \in L$"? Könntest du eine Turingmaschine bauen, die in endlicher Zeit herausfindet, falls $w \in L$ gilt, deren Verhalten aber unbestimmt ist, falls $w$ nicht aus $L$ ist, dann ist das Problem semi-entscheidbar. Ist das Problem aber entscheidbar, so kann die Turingmaschine in endlicher Zeit ausgeben, ob $w$ aus $L$ ist oder nicht.

Man erkennt also, dass ein Problem nur dann entscheidbar sein kann, wenn es "in beide Richtungen" semi-entscheidbar ist. entscheidbare Probleme sind also, wie du schon richtig sagtest, eine Teilmenge der semientscheidbaren.

Philippe (Tutor)

Beantwortet 26, Nov 2014 von uafjv uafjv Tutor(in) (167,990 Punkte)  
Bearbeitet 9, Dez 2014 von Lukas König
...