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

Sind in semientscheidbaren Problemen auch unentscheidbare Probleme enthalten?

0 Punkte
55 Aufrufe
Rein theoretisch könnten dort ja auch Probleme enthalten sein, wo wir nur denken, sie würden sich irgendwann in 1000 Jahren als entscheidbar erweisen, aber es eigentlich gar nicht sind?

Oder können wir darüber überhaupt keine Aussage treffen, weil es sich nicht ausfindig machen lässt, ob ein untentscheidbares Problem enthalten ist?
Gefragt 9 Feb in BER-AA von uuuwm uuuwm Lernwillige(r) (160 Punkte)  

Eine Antwort

0 Punkte
Hallo,

bei semi-entscheidbaren Problem erhält man für eine richtige Eingabe, das Ergebnis true. Nur bei einer falschen Eingabe kann das Programm unendlich weiterlaufen oder false zurückgeben. (Kapitel 5 Folie 17)

Bei einer richtigen Eingabe würde eine Turingmaschine stoppen. Dadurch kann ein semi-entscheidbares Problem von einem unentscheidbaren Problem unterschieden werden.

Ich hoffe ich konnte dir weiterhelfen.

Viele Grüße,

Verena (Tutorin)
Beantwortet 10 Feb von upfgy upfgy Eins-Komma-Null-Anwärter(in) (1,820 Punkte)  
Hey Verena, danke für deine schnelle Antwort. Also ist die Antwort auf meine Frage aus dem Betreff ein "JA"?
...