rekursionssatz < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:55 Mi 10.01.2007 | | Autor: | AriR |
hey leute
wir haben in der vorlesung den rekursionssatz durchgenommen, nur leider verstehe ich nicht genau, was sich dahinter verbirgt.
wir haben den satz folgendermaßen eingeführt:
Ist g eine n + 1stellige partiellrekursive Funktion, so gibt es einen
Index e(welches eine Gödelnummer einer partielle rek.fkt ist), der die Gleichung [mm] {e}^n(x_1, [/mm] . . . , [mm] x_n)\cong [/mm] (partiell gleich) g(e, [mm] x_1, [/mm] . . . , [mm] x_n) [/mm] löst.
dene wiki artikel habe ich auch gelesen, nur leider sehe ich das dort beschriebene in unserem satz nicht.
in dem wiki artikel steht soweit ich das verstanden habe, dass dass wenn man ein modifikationsprogramm was glaub ich in diesem fall das g wäre hat, kann man immer eine fuktion finden in unserem fall die funktion, die durch die gödelnummer e gegeben ist, und wenn man g auf e und seine argumente [mm] x_1,...,x_n [/mm] loslässt, dann kommt immer noch [mm] {e}^n(x_1,...,x_n) [/mm] heraus, wobei [mm] {e}^n [/mm] hier die funktion sein soll, die durch die gödelnummer e gegeben ist.
ich hab jetzt leider keine ahnung, ob ich das richtig verstanden habe.
Ich hoffe mir kann jemand von euch weiterhelfen.
Gruß Ari :)
|
|
| |
|
Hallo und guten Morgen,
schau zB bei Egon Börger, ''Berechenbarkeit, Komplextität, Logik'' nach oder in einem Buch zur Rekursionstheorie von Soare.
Bei Deiner Formulierung ist g das Programmmodifikationsprogramm, und e ist dann der Fixpunkt, d.h. dasjenige
Programm, das durch Anwendung von g in seiner Funktionalität nicht verändert wird.
Der Beweis des Rekursionstheorems, obwohl extrem kurz, gehört zu den eher schwer zu verstehenden
Dingen der elementaren Rekursionstheorie, und effiziente Versionen finden zB Anwendung bei
nichtdeterministischen Zeithierarchien.
Es gibt auch ein Buch von Rogers ''Rekursionstheorie'', das zwar alt, aber dennoch lesenswert ist und auch einen
guten Abschnitt über das Rekursionstheorem umfaßt.
bei Soare ist nachzulesen, daß man sich den Beweis des Rekursionstheorems als fehlgeschlagenen Diagonalisierungsversuch zum Beweis des Gegenteils illustrieren kann.
Gruss,
Mathias
|
|
|
|
