Grundzüge der Theoretischen Informatik Markus Bläser

News

Gödelisierung Teil 2

Written: 19.11.2018 14:20 Written By: Markus Bläser

Die Gödelisierungsfunktion, die momentan im Script steht, ist leider nicht wie behauptet bijektiv, sondern nur injektiv. Die ganze Theorie wuerde auch mit einer injektiven Funktion funktionieren (und hat sie auch in all den Jahren davor), wenn dann aber später Reduktionen eingeführt werden, muss man eine Reihe von einfachen, aber hässlichen Fallunterscheidungen machen. Daher kommt die Umstellung auf eine (bald) bijektive Gödelisierung.  Wir werden das ganze wie folgt reparieren (und gleichzeitig eine weitere nicht so schoene Stelle im Skript verbessern): Konkatenation von Programmen wird geklammert. Damit ist die Semantik Phi_P automatisch wohldefiniert. Und danach werden wir zeigen, dass Konkatenation bzgl. Semantik assoziativ ist, dass heisst, in der Praxis koennen wir die Klammern immer weglassen. Ausser den angesprochenen Dingen wird sich damit im Skript nichts weiter aendern.

Ich werde das Skript im Laufe der Woche umschreiben und auch am Mittwoch etwas dazu in der Vorlesung sagen. Die Umstände tun wir leid, aber ich denke, dass insgesamt das Skript besser wird.



Datenschutz | Impressum
Bei technischen Problemen wenden Sie sich bitte an die Administratoren