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

Entscheidbarkeit von Problemen

+1 Punkt
96 Aufrufe
zu 7) Inwiefern ist nicht jede abzählbare Menge auch entscheidbar? Wie würde man das begründen?

zu b) Die Menge der nichtentscheidbaren Probleme überlappt also nur teilweise die Menge der semi-entscheidbaren Probleme ohne die Menge der entscheidbaren Probleme zu berühren. Kann man sich das so zu der Zeichnung dazudenken?

Dann gibt es

1. entscheidbare Probleme

2. semi-entscheidbare und nicht nichtentscheidbare Probleme

3. semi-entscheidbare und nichtentscheidbare Probleme (wie das Halteproblem für Turing-Maschinen)

4. nichtentscheidbare Probleme (wie L_NA).

Oder sind die 1. und die 2. Menge gleich, sodass die Menge der nichtentscheidbaren Probleme eine Ellipse außerhalb der semientscheidbaren Probleme ist ohne die der entscheidbaren Probleme?

 

LG
bezieht sich auf eine Antwort auf: Erklärungsveruche zu den Fragen
Gefragt 15, Nov 2014 in BER-AB von uyctv uyctv Info-Genie (19,250 Punkte)  

2 Antworten

0 Punkte
Dass nicht jede abzählbare Menge auch entscheidbar ist, begründet man entweder durch Angabe einer Menge, die abzählbar, aber nicht entscheidbar ist (bspw. Menge der haltenden Turingmaschinen / Sprache L_NA) oder durch die Aussage, dass es nur abzählbar viele Algorithmen gibt, aber überabzählbar viele abzählbare Mengen, sodass es nicht zu jeder abzählbaren Menge ein Entscheidungsverfahren geben kann. (Schauen Sie sich das nochmal auf den Vorlesungsfolien an!)

Ihre Mengenaufzählung verstehe ich nicht. Die Hierarchie ist so, wie auf Folie 7 der Saalübung dargestellt.

Das Halteproblem ist dabei in der Menge der semi-entscheidbaren, aber nicht in der Menge der entscheidbaren Probleme (oder Sprachen). Die Sprache L_NA ist in der Menge p(E*) (wie alle Sprachen), aber nicht in der Menge der semi-entscheidbaren Sprachen.

Viele Grüße

Lukas König
Beantwortet 15, Nov 2014 von uyctv uyctv Info-Genie (19,250 Punkte)  
0 Punkte
Hallo,

ich verstehe jetzt erst, was Sie mit diesen Mengen (1-4) meinen. Daher doch noch der Nachtrag zu dieser Frage:

"Oder sind die 1. und die 2. Menge gleich, sodass die Menge der nichtentscheidbaren Probleme eine Ellipse außerhalb der semientscheidbaren Probleme ist ohne die der entscheidbaren Probleme?"

Die 1. und 2. Menge sind in der Tat gleich. Nicht entscheidbar sind einfach alle Mengen, die außerhalb der Menge der entscheidbaren Probleme liegen. Diese können semi-entscheidbar (bspw. Halteproblem) oder nicht semi-entscheidbar (also auch noch außerhalb dieser Menge in p(E*); bspw. L_NA) sein.

Viele Grüße

Lukas König
Beantwortet 15, Nov 2014 von uyctv uyctv Info-Genie (19,250 Punkte)  
...