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

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

0 Pluspunkte 0 Minuspunkte
131 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 :)
in BER-AA von uhevv uhevv Lernwillige(r) (1.3k Punkte)  
Bearbeitet von uhevv uhevv

1 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ß
von udjza udjza Lernwillige(r) (800 Punkte)  
ausgewählt von uhevv uhevv
0 0
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
...