Diskussion:Rekursionssatz

Ist dies nicht der Fixpunktsatz von Kleene? Der Rekursionssatz sagt doch aus, dass man Argumente von Programmen fest in den Quellcode einprogrammieren kann.

Evolux 01:54, 6. Jan 2006 (CET)

Fehler meinerseits, beide Begriffe sind identisch. Ich werde die Artikel vereinigen. Evolux 16:59, 14. Jan 2006 (CET)

Auf der englischen Wikipedia gibt es zwei getrennte Artikel en:Kleene's recursion theorem und en:Kleene fixpoint theorem. Haben die was hiermit zu tun? --Abdull 19:27, 22. Feb 2006 (CET)

Trotz der langen Zeitspanne hier die Antwort auf die obige Frage:

Eigentlich ist Kleene's Recursion Theorem etwas umfassender, denn es besagt, dass es eine injektive berechenbare Funktion gibt, die bereits aus der Gödelnummer einer Funktion deren semantischen Fixpunkt (oder sogar noch weitergehende Manipulationen) bestimmen kann. Der hier angebene Fixpunktsatz ergibt sich dann als triviales Korollar. So gesehen handelt es sich also um zwei verschiedene Sätze der Berechenbarkeitstheorie.

Der in en:Kleene fixpoint theorem behandelte Satz ist dagegen im Bereich der Verbandstheorie angesiedelt. Er basiert zwar auf den Arbeiten von Kleene zur Berechenbarkeit, behandelt aber ein völlig anderes Phänomen.

-- 86.56.10.166 18:58, 16. Jul. 2013 (CEST)

Kann es sein, dass es unter Anwendungen heißen muss f(x): return + x ? Dann wäre für Fixpunkt M nämlich M=f(M)= return M , d.h. M gibt seinen Code aus (nicht signierter Beitrag von 94.220.54.127 (Diskussion) 16:14, 18. Feb. 2012 (CET))

Allgemeinerer Satz

Gerade in der englischsprachigen Literatur wird was hier als Fixpunktsatz von Kleene firmiert H. Rogers Jr. zugeschrieben (mit Verweis auf §11.2 seiner Theory of Recursive Functions and Effective Computability von '67) und Kleene's Recursion Theorem wie folgt angegeben:

Sei $\{\varphi _{i}\}_{i\in \mathbb {N} }$ eine effektive Nummerierung aller partiell berechenbarer Funktionen.

Für jede partiell berechenbare Funktion $f\in {\mathcal {P}}$ existiert ein Index $e$, so dass $\forall x\colon \varphi _{e}(x)=f(e;x)$.

Zwar ist diese Fassung (trotz der scheinbar allgemeineren Aussage) äquivalent zum Fixpunktsatz, aber es wäre m.M.n. sinnvoll diese ebenfalls in den Artikel zu integrieren. Bspw. verwendet jeder Beweis den ich kenne, der sich auf KRT stützt, die obige Fassung, sei es in der Berechenbarkeitstheorie oder der Algorithmischen Lerntheorie. Die Version ist flexibler und im Gegensatz zur Fixpunktfassung gilt sie auch noch für einige Nummerierungen partieller Funktionen die schwächer sind als das acceptable programming system $\varphi$.

Für einen Edit des Artikels fehlt mir aber noch eine entscheidende Information: Kleene hat natürlich seine Arbeiten deutlich früher als Rogers veröffentlicht. Die Frage ist, fand Rogers seine Version dennoch unabhängig vom Werk Kleenes und gibt es dafür belastbare Quellen. (Ich besitze leider nur die überarbeitete Ausgabe der Theory von '87.) Sollte der Fixpunktsatz (historisch) dagegen ein blosses Korollar von KRT sein, dann muss erst recht obige Fassung in den Artikel.

Liebe Grüsse

--158.181.86.62 18:18, 1. Mär. 2015 (CET)

Update: Rogers waren die Arbeiten von Kleene (erwartungsgemäss) bekannt, er beschrieb den Fixpunktsatz explizit als "einfachere Fassung" (H. Rogers Jr.: Theory of Recursive Functions and Effective Computability; McGraw-Hill; 1967; p. 179). Werd den Artikel mal erweitern. Kann aber ein bisschen dauern, da ich noch zeitlich gebunden bin.

-- 84.19.199.240 19:01, 8. Mär. 2015 (CET)