General recursive functions of natural numbers

S. C. Kleene

doi:10.1007/bf01565439

journal article Dec 01, 1936

General recursive functions of natural numbers

S. C. Kleene

Mathematische Annalen Vol. 112 No. 1 pp. 727-742 · Springer Science and Business Media LLC

View at Publisher Save 10.1007/bf01565439

Topics

No keywords indexed for this article. Browse by subject →

References

18

[1]

W. Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Math. Annalen99 (1928), S. 118–133; Rózsa Péter, Konstruktion nichtrekursiver Funktionen, Math. Annalen111 (1935), S. 42–60. 10.1007/bf01459088

[2]

In the “functions” which we consider, the arguments are understood to range over the natural numbers (i. e. non-negative integers) and the values to be natural numbers. Also, for abbreviation, we use propositional functions of natural numbers, calling them “relations” (alternatively “classes”, when there is only one variable) and employing the following notations:(x) A (x) [for all natural numbers,A (x)], (E x) A (x) [there is a natural numberx such thatA (x)], εx [A (x)] [the least natural numberx such thatA (x), or 0 if there is no such number], — [not], ∀ [or], & [and],→[implies], ≡[is equivalent to].

[3]

Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I

Kurt Gödel

Monatshefte f�r Mathematik 1931 10.1007/bf01700692

[4]

This form of the definition was introduced by Gōdel to avoid the necessity of providing for omissions of arguments on the right in schemas (1) and (2). The operations in the construction of primitive recursive functions can be further restricted. See Rózsa Péter, Über den Zusammenhang der verschiedenen Begriffe der rekursiven Funktionen, Math. Annalen110 (1934), S. 612–632. 10.1007/bf01448046

[5]

In these operations we do not require thatA andB=C be equations and that σ be a functional variable, since R1−R3 as stated when applied to equations generate equations. Thereby, our proof of IV is simplified.

[6]

In what follows, the word “recursive” (when not qualified by the adjective “primitive”) will mean recursive under any one of the definitions 2a, 2b and 2c, except when the definition involved is mentioned explicitly (as is necessary in the course of establishing the theorems VI and IX on their equivalence).

[7]

A more general definition would not be obtained by allowing under R3 also the substitution ofB forC, sinceE may be chosen to includeb=a whenevera=b is included.

[8]

Similarly, the equations of the systemE of Def. 2b are verifiable by use of the values under Def. 2b, if they are of the form σ(a 1, ...,a 8)=b.

[9]

Also see Th. Skolem, Begründung der elementaren Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbarer Veränderlichen mit unendlichem Ausdehnungsbereich, Videnskapsselskapets Skrifter 1923. I. Mat. naturv. Kl., Nr. 6, S. 1–38.

[10]

Note thatl(I)=0 andx*1=1*x=x[l(x)>0].

[11]

Ifk=0, replace “λ(0,z)=l(z)” by “λ(0,z)=1” in the definition of θ(z, m).

[12]

Besides the method, for demonstrating that a function is not primitive recursive (or not definable by given additional means, such as recursions with respect ton variables simultaneously), which consists in finding a lower bound for the values, we have the method, for demonstrating relationships of the opposite kind, which consists in finding an upper bound for the number of steps in the computation algorithm.

[13]

In XV below is given an example (Ey)T 1 (x, x, y) of a non-recursive class which by III is recursively enumerable.

[14]

Since the means given for passing from definitions under Def. 2a (2b) to definitions under Def. 2c, and vice versa, are effective, the problem which we now study (which numbers define functions recursively) is equivalent to the one first proposed (which systems of equations define functions recursively).

[15]

The undecidable propositionA f can be effectively constructed for a given logic, whenever the numbera k , recursive definitions ofA (x); x, y B z; β(y) andC (n), and effective means of constructingA f fromf, are given. Whenever the supposition in this proof, that there is ak such thatA k is provable, is not realized, the theorem holds trivially.

[16]

From the great generality of the problems, whiche's define recursively functions of one variable, and whiche's “determine recursively” thee th value of a function of one variable, as displayed by this theorem, the result, that they are not “effectively” soluble, could have been anticipated.

[17]

E. g. (x 1,x 2,x 3)R (x 1,x 2,x 3) ≡(x) (Ey) [R(1Gl x, 2Gl x, 3Gl x)≡&y=y].

[18]

XV, XVI, and XVII are similar, respectively, to results obtained in a different connection by Prof. Alonzo Church (An unsolvable problem of elementary number theory, see Bull. Amer. Math. Soc. Abstract41-5-205), Dr. J. B. Rosser (unpublished), and the present writer (A theory of positive integers in formal logic, Part II, Amer. Jour. Math.57 No. 2, pp. 230 ff.).

Cited By

291

Limitations of Deep Learning for Inverse Problems on Digital Hardware

Holger Boche, Adalbert Fono · 2023

IEEE Transactions on Information Th...

Effective procedures in field theory

Albrecht Fröhlich, J. C. Shepherdson · 1956

Philosophical Transactions of the R...

Nicht konstruktiv beweisbare Sätze der Analysis

Ernst Specker · 1949

The Journal of Symbolic Logic

Metrics