c) Frage 3 Verständnis

Question

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!

Comments

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

---

Entschuldigung, ja genau ich meinte Aufgabe 97c) Kap.10 im Übungsbuch.
Vielen Dank für Ihre ausführliche Antwort!

Answer 1

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.