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
154 Aufrufe

Hallo,

die Formulierung der Antwort "eine Menge ist abzählbar aber nicht aufzählbar" ist für mich nicht klar. Was meint man denn genau mit "der Menge aller TM, die auf ihrer eigenen Kodierung als Eingabe nicht halten"?

Sobald eine TM ihre "eigene Sprache" liest, gelangt sie doch in den Endzustand und hält an, oder?

Vielen Dank im Voraus!

in BER-AG von uqebf uqebf Lernwillige(r) (170 Punkte)  
Kategorie geändert von
0 0
Auf welche Aufgabe beziehen Sie sich denn? BER-AG? Ich habe mal Ihre Frage auf Verdacht in diese Kategorie verschoben, falls es nicht stimmt, bitte ich Sie, sie selbst an die richtige Stelle zu verschieben (durch Klicken auf "Bearbeiten").
0 0
Entschuldigung, ja genau ich meinte Aufgabe 97c) Kap.10 im Übungsbuch.
Vielen Dank für Ihre ausführliche Antwort!

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

Die Kodierung einer Turingmaschine hat nichts mit der Sprache zu tun, die sie erkennt. Jede Turingmaschine kann durch ein einziges Wort kodiert werden; dieses Wort steht dann für diese Turingmaschine und kann von einer anderen Turingmaschine (oder auch derselben) als Eingabe eingelesen werden.

Die Sprache einer Turingmaschine besteht dagegen normalerweise aus unendlich vielen Wörtern.

Man kann sich jetzt bspw. die Frage stellen: Gibt es eine Turingmaschine, deren Sprache aus den (unendlich vielen) Kodierungen derjenigen Turingmaschinen besteht, die (auf einer bestimmten Eingabe, welche ebenfalls gegeben oder fix festgelegt sein kann) anhalten, also nicht in einer Endlosschleife landen? Das wäre so in etwa die Formulierung des Halteproblems, von dem Sie aus der Vorlesung wissen, dass es nicht entscheidbar, aber immerhin semientscheibar (oder "aufzählbar") ist. Das heißt, dass es so eine Turingmaschine zwar gibt, aber dass diese nicht für alle Eingaben garantiert anhält, sondern nur für diejenigen, die tatsächlich in der Sprache sind.

In der Aufgabe ist aber nach einem noch schwierigeren Problem gefragt, nämlich nach einem, das nicht einmal aufzählbar/semientscheidbar ist, für das es also GAR KEINE Turingmaschine gibt, die nur Instanzen dieses Problems akzeptiert. Wir hatten als ein Beispiel einer nicht aufzählbaren formalen Sprache die Diagonalsprache $L_{NA}$ kennengelernt. Eine formale Sprache ist natürlich immer abzählbar, also erfüllt $L_{NA}$ die Anforderung aus der Aufgabe und hätte dort auch einfach als Lösung angegeben werden. Nun kann $L_{NA}$ noch ein bisschen einfacher kostruiert werden, wie wir das im Lehrbuch (www.dasinfobuch.de, ab Seite 295) tun. Dabei kommt gerade die "Menge der Kodierungen aller Turingmaschinen, die auf ihrer eigenen Kodierung als Eingabe nicht halten" heraus, also die Antwort, die in der Übungsaufgabe gegeben wird.

Interessant ist hierbei zu bemerken, dass die Frage, ob eine Turingmaschine auf einer Eingabe nicht hält, wesentlich schwieriger ist als die Frage, ob sie hält. Diese Unterscheidung ist es, die den Sprung aus der Semientscheidbarkeit in die völlige Unentscheidbarkeit vollbringt. Warum ist das eigentlich so? Denken Sie mal darüber nach... Es ist wichtig, das verstanden zu haben - auch im Hinblick auf die (sicher wieder vorkommende) Komplexitätsaufgabe in der Klausur.

von Dozent (10.1m Punkte)  
Bearbeitet von
...