nach oben

Erschienen in:

2022 | OriginalPaper | Buchkapitel

9. The Second Recursion Theorem

verfasst von : George Tourlakis

Erschienen in: Computability

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The recursion theorem is attributed to Kleene, but it was embedded in a somewhat different format in Gödel’s first incompleteness theorem proof (Gödel (Monatshefte für Math Phys 38:173–198)), where, via his substitution function and the fixed point lemma, he constructed a sentence of Peano Arithmetic (PA) that said “I am not a theorem”.

The analogues in Kleene’s proof of his second recursion theorem (He has also stated and a proved a “first recursion theorem”. See Chap. 13.) are the S-m-n functions (instead of the Gödel substitution function) and the second recursion theorem itself (instead of the fixpoint lemma of Gödel (Monatshefte für Math Phys 38:173–198); Carnap (Logische Syntax der Sprache (Springer, Berlin, 1934))).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Gödel’s First Incompleteness Theorem via the Halting Problem

Nächstes Kapitel A Universal (non-) Function for

He has also stated and a proved a “first recursion theorem”. See Chap. 13.

Introduced as a, provably within formal arithmetic, primitive recursive function.

Actually the fixed point lemma entered only implicitly in Gödel’s proof in Gödel (1931), but Carnap (1934) teased it out and explicitly formulated it.

Also known as the diagonalisation lemma (or diagonal lemma in Boolos 1979).

There is a convergent computation of y steps of the i-th URM that verifies input x.

Functions viewed extensionally have, as we know, infinitely many ϕ-indices (see also Corollary 9.4.2 below). However, we allow the definite article “the” here thinking rather of the intentional object for our \(\lambda z\vec x_{n}.f\big (S^{n}_{1}(z, z), \vec x_{n}\big )\) —i.e., the URM at location i— and also of the URM at location \(S^{n}_{1}(i, i)\) that computes \(\lambda \vec x_{n}.f\big (S^{n}_{1}(i, i), \vec x_{n}\big )\). Cf. Theorem 5.7.1 and its corollaries, in particular Corollary 5.7.3.

As distinguished from the fixed point theorem of PA.

The lay person —also, Sherlock Holmes— will say “elementary” as a synonym for “easy”. Mathematicians use the term more technically. They mean that the tools used in the proof are “not advanced” —but the task may still be very hard. E.g., the prime number theorem, that says \(\lim _{x\to \infty }\frac {\pi (x)}{x/\log x}=1\) has a proof that uses complex variable calculus and one that does not. Arguably, the latter is harder, but it is called the “elementary” one.

G. Boolos, The Unprovability of Consistency; An Essay in Modal Logic (Cambridge University Press, Cambridge, 1979)MATH

R. Carnap, Logische Syntax der Sprache (Springer, Berlin, 1934)CrossRef

K. Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Math. Phys. 38, 173–198 (1931) (Also in English in M. Davis, The Undecidable (Raven Press, Hewlett, 1965), pp. 5–38)

Y.N. Moschovakis, Kleene’s amazing second recursion theorem. Bull. Symb. Logic 16(2), 189–239 (2010)MathSciNetCrossRef

A.A. Muchnik, Solution of Post’s reduction problem and of certain other problems in the theory of algorithms. I (Russian). Tr. Mosk. Mat. Obs. 7, 391–405 (1958)

H. Rogers, Theory of Recursive Functions and Effective Computability (McGraw-Hill, New York, 1967)MATH

R.M. Smullyan, Theory of Formal Systems. Number 47 in Annals of Math. Studies (Princeton University Press, Princeton, 1961)

O. Veblen, J.W. Young, Projective Geometry, vol. I (Ginn and Company, Boston, 1916)MATH

R.L. Wilder, Introduction to the Foundations of Mathematics (Wiley, New York, 1963)

Titel: The Second Recursion Theorem
verfasst von: George Tourlakis
Verlag: Springer International Publishing
Buch: Computability
Print ISBN: 978-3-030-83201-8

Electronic ISBN: 978-3-030-83202-5

Copyright-Jahr: 2022
DOI: https://doi.org/10.1007/978-3-030-83202-5_9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"