Verständnisfrage zur Notation: L = {<M> | M det. 1-Band TM, M hat Eigenschaft A}

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Verständnisfrage zur Notation: L = { | M det. 1-Band TM, M hat Eigenschaft A}
Die Sprache L definiert nach der Überrschrift die Menge aller Gödelnummer, aller 1-Band-TM, die eine Eigenschaft A haben.
Beispiel für Eigenschaft A, M hält (mindestens / genau / höchstens) für Quadratzahlen.

Hier muss M keine feste TM sein, oder? M_1, M_2 können für verschiedene endliche, unterschiedliche große Alphabete B_1 und B_2 definiert sein und trotzdem Eigenschaft A haben, oder?
Kann die Gödelisierung von M_1, M_2 zufällig diesselbe sein?

Ich wäre dankbar für jeden konstruktiven Kommentar bzw. Antwort.


Die Gödelisierung von zwei unterschiedlichen Maschinen muss natürlich unterschiedlich sein. Möglicherweise müsste noch eine Encodingvorschrift für ein eventuell anderes Eingabealphabet vorhanden sein, o.ä., da sonst die Maschine überhaupt nicht interpretiert (z.b. emuliert) werden könnte.

Edit: Um es mal anders zu formulieren: Es muss irgendwie für die “äußere” Maschine möglich sein, die “innere” auszuführen. Wie das passiert hängt von der Gödelcodierung, von der Alphabetscodierung etc. ab. Aber es muss eine (“universelle”) Maschine schreibbar sein die die “innere” Maschine emuliert/rekursiv aufzählt.

1 Like

Ist es nicht möglich, dass dann die Menge aller DTM, die Eigenschaft A haben mächtiger ist als {#,0,1}* ?
Außerdem: Wenn L “nur” eine Menge von Gödelnummern ist, dann sollte sie auch trivial rekursiv aufzählbar sein. Eine surjektive Abbildung von {0,1}* → L = {0,1,#}* ist dann trivial gegeben, es könnte dann höchstens noch am total berechenbar scheitern, aber die Eigenschaft ist sowieso fast immer erfüllt.


Die Menge aller TM ist einfach durch ihr Tupel definiert. Das ist völlig unabhängig von {#,0,1}. {#,0,1} ist allein eine Eigenschaft der bestimmten Gödelisierung aus der Vorlesung. Genausogut könnte man eine TM auch in {0,1}* oder sogar {1}* abbilden. Ob ein bestimmtes Wort nach einer bestimmten Gödelisierung eine valide TM darstellt ist sogar entscheidbar (Syntaxanalyse), nicht nur RA.

Am einfachsten ist es bei Beweisen mit solchen Maschinen immer von einer festen Gödelisierung mit festen Alphabeten etc. auszugehen. So ist der semantische Sinn einer bestimmten Gödelnummer immer klar.

Diese Semantik der Gödelisierung muss irgendwo definiert sein, sonst ist die Gödelnummer einfach ein unverständlicher string aus Zeichen und kann nicht von der UTM emuliert werden.