Entscheidbarkeit von Problemen

Question

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

Answer 1

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

Answer 2

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