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

Knoten im Kopf bzgl. Entscheidbarkeit

0 Pluspunkte 0 Minuspunkte
111 Aufrufe
Ich habe gerade ein Problem zwei (vermeintliche) Erkenntnisse unter einen Hut zu bringen:

1. Reelle Intervalle sind überabzählbare Mengen

2. Jede entscheidbare Menge ist auch abzählbar (woraus folgt, dass jede überzählbare Menge nicht entscheidbar ist)

Somit dürften reelle Intervalle nicht entscheidbar sein. Liege ich soweit richtig?

Jetzt zu dem Punkt der mir Kopfzerbrechen macht:

Wenn mir jemand eine beliebige reelle Zahl z sagt und mich fragt, ob diese in einem beliebig gegebenen reellen Intervall [a, b] liegt, dann kann ich das doch auf relativ simple Weise algorithmisch beantworten indem ich z.B. zuerst prüfe ob z >= a und dann ob z <= b. Ich kann also immer sagen "Ja, z ist im Intervall" bzw. "Nein, z ist nicht im Intervall". Das fühlt sich für mich sehr nach Entscheidbarkeit an.

Wo ist mein Denkfehler? Freue mich über jegliches Input!

Wenngleich die Klausur schon vorbei ist, würde ich mich trotzdem freuen, wenn jemand hierzu Gedanken oder sogar eine Erklärung hat :)
Gefragt 10 Feb in BER-AA von uhevv uhevv Lernwillige(r) (1,330 Punkte)  
Bearbeitet 11 Feb von uhevv uhevv

Eine Antwort

0 Pluspunkte 0 Minuspunkte
 
Beste Antwort
Hi,

ich glaube du schmeißt da zwei Sachen in einen Topf, die nicht zusammen gehören, bzw. die nicht wirklich was miteinander zu tun haben.

Wenn du ein Intervall hast, schaust du dir zwei seperate Grenzen, die eindeutig bestimmbar sind. Durch den angesprochenenen Algorithmus, kannst du nun entscheiden, ob die reele Zahl darin liegt oder nicht. In diesem Schritt musst du allerdings nichts abzählen, aufzählen oder sonstiges, sondern nur ein Vergleich tätigen. Das hat dann ja im Kern nichts mit der Art der Menge im Intervall zu tun, da diese dafür unerheblich ist (außer natürlich diese unterscheidet sich von der Zahlenart der reelen Zahl). Es ist ja egal ob, das jetzt ein natürliches Intervall, rationales Intervall oder sontiges ist, der Vergleich bleibt im Prinzip gleich.

Du hast in dieser Unterscheidung auch keine Menge die abzählbar/aufzählbar/überabzählbar ist, sondern eine ja/nein Antwort, die nicht in direktem Kontext mit dem Zahlenintervall steht, sondern sich nur als eine Folgerung daraus ergibt.

Hoffe ich konnte meine Gedanken dazu rüberbringen, wobei ich auch nicht weiß, ob ich da richtig bin. Kann gerne berichtigt werden,

Gruß
Beantwortet 11 Feb von udjza udjza Lernwillige(r) (800 Punkte)  
ausgewählt 12 Feb von uhevv uhevv
Hmm okay. Erstmal danke für die Antwort!
Leider hat deine Antwort bei mir noch zu keinem restlosen Verständnis der Lage geführt.
Dass man etwas abzählt, aufzählt oder sonstiges ist (zumindest meiner bisherigen Auffassung nach) laut unseren Vorlesungsfolien für die Betrachtung, ob eine Menge entscheidbar ist nicht gefordert. Damit eine Menge entscheidbar ist muss ihre charakteristische Funktion berechenbar sein und damit eine Funktion berechenbar ist muss es einen Algorithmus geben der das selbe Verhalten aufweist wie die Funktion (Etwas salopp ausgedrückt). Einen solchen Algorithmus haben wir ja durch den oben beschriebenen Alg. gegeben, somit müsste die charakteristische Funktion eines reellen Intervalls berechenbar und dieses somit auch entscheidbar sein.
Dass das nicht sein kann sehe ich ein. Schließlich haben wir ja bewiesen, dass reelle Intervalle überabzählbar sind. Nur sehe ich bisher noch nicht, wo in meiner Argumentation der Fehler liegt
...