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

1 Pluspunkt 0 Minuspunkte
114 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
in BER-AB von uyctv uyctv Info-Genie (21.1k Punkte)  

2 Antworten

0 Pluspunkte 0 Minuspunkte
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
von uyctv uyctv Info-Genie (21.1k Punkte)  
0 Pluspunkte 0 Minuspunkte
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
von uyctv uyctv Info-Genie (21.1k Punkte)  
...