This section is longer and more detailed than the others because of its importance to the topic: Kleene was the first to propose that
all calculations/computations—of
every sort, the
totality of—can
equivalently be (i)
calculated by use of five "
primitive recursive operators" plus one special operator called the
mu-operator, or be (ii)
computed by the actions of a Turing machine or an equivalent model. Furthermore, he opined that either of these would stand as a definition of
algorithm. A reader first confronting the words that follow may well be confused, so a brief explanation is in order.
Calculation means done by hand,
computation means done by Turing machine (or equivalent). (Sometimes an author slips and interchanges the words). A "function" can be thought of as an "input-output box" into which a person puts natural numbers called "arguments" or "parameters" (but only the counting numbers including 0—the nonnegative integers) and gets out a single nonnegative integer (conventionally called "the answer"). Think of the "function-box" as a little man either calculating by hand using "general recursion" or computing by Turing machine (or an equivalent machine). "Effectively calculable/computable" is more generic and means "calculable/computable by
some procedure, method, technique ... whatever...". "General recursive" was Kleene's way of writing what today is called just "recursion"; however, "primitive recursion"—calculation by use of the five recursive operators—is a lesser form of recursion that lacks access to the sixth, additional, mu-operator that is needed only in rare instances. Thus most of life goes on requiring only the "primitive recursive functions."
1943 "Thesis I", 1952 "Church's Thesis" In 1943 Kleene proposed what has come to be known as
Church's thesis: : "
Thesis I. Every effectively calculable function (effectively decidable predicate) is general recursive" (First stated by Kleene in 1943 (reprinted page 274 in Davis, ed.
The Undecidable; appears also verbatim in Kleene (1952) p.300) In a nutshell: to calculate
any function the only operations a person needs (technically, formally) are the 6 primitive operators of "general" recursion (nowadays called the operators of the
mu recursive functions). Kleene's first statement of this was under the section title "
12. Algorithmic theories". He would later amplify it in his text (1952) as follows: : "Thesis I and its converse provide the exact definition of the notion of a calculation (decision) procedure or
algorithm, for the case of a function (predicate) of natural numbers" (p. 301, boldface added for emphasis) (His use of the word "decision" and "predicate" extends the notion of calculability to the more general manipulation of symbols such as occurs in mathematical "proofs".) This is not as daunting as it may sound – "general" recursion is just a way of making our everyday arithmetic operations from the five "operators" of the
primitive recursive functions together with the additional
mu-operator as needed. Indeed, Kleene gives 13 examples of primitive recursive functions and Boolos–Burgess–Jeffrey add some more, most of which will be familiar to the reader—e.g. addition, subtraction, multiplication and division, exponentiation, the CASE function, concatenation, etc., etc.; for a list see
Some common primitive recursive functions. b, :# Factorial a! : 0! = 1, a'! = a!*a' :# Decrement: "predecessor of a" defined as "If a > 0 then a − 1 → anew else 0→a." :# Proper subtraction: a┴b defined as "If a ≥ b then a − b else 0." :# Minimum (a1, ... an) :# Maximum (a1, ... an) :# Absolute value: | a − b | =defined a┴b + b┴a :# ~sg(a): NOT[signum(a}]: If a=0 then sg(a)=1 else if a>0 then sg(a)=0 :# sg(a): signum(a): If a=0 then sg(a)=0 else if a>0 then sg(a)=1 :# Remainder (a,b): the leftovers if b does not divide a "evenly" :# "b divides a" [a|b]: If the remainder (a,b)=0 then [a|b] else b does not divide a "evenly" :# s = b: sg | a − b | :# a def a>1 & NOT(Exists c)1 [c|a] :# Pi: the i+1-st prime number :# (a)i : exponent ai of pi =def μx [ x [pix|a & NOT(pi x'|a ]; here μx is the minimization operator :# lh(a): the "length" or number of non-vanishing exponents in a :# a*b: given the expression of a and b as prime factors then a*b is the product's expression as prime factors : ''In the following the abbreviations
x =def xi, ... xn; subscripts may be applied if the meaning requires. • #A: A function φ definable explicitly from functions Ψ and constants q1 , ... qn is primitve recursive in Ψ. • #B: The finite sum Σy ψ(
x, y) and product Πyψ(
x, y) are primite recursive in ψ. • #C: A predicate P obtained by substituting functions χ1 ,..., χm for the respective variables of a predicate Q is primitive recursive in χ1 ,..., χm, Q. • #D: The following predicates are primitive recursive in Q and R: ::* NOT_Q(
x) . ::* Q OR R: Q(
x) V R(
x), ::* Q AND R: Q(
x) & R(
x), ::* Q IMPLIES R: Q(
x) → R(
x) ::* Q is equivalent to R: Q(
x)≡ R(
x) • #E: The following predicates are primitive recursive in the predicate R: :: (Ey)y R(
x, y): (Ey) denotes "there exists at least one y such that" :: (y)y R(
x, y): (y) denotes "for all y it is true that" :: μyy R(
x, y): μ is the minimization operator "the least value of y such that R(
x, y) is true" • #F: Definition by cases: The function defined thus, where Q1, ..., Qm are mutually exclusive predicates (or "ψ(
x) shall have the value given by the first clause which applies), is primitive recursive in φ1, ..., Q1, ... Qm: :: φ(
x) = ::* φ1(
x) if Q1(x) is true, ::* . . . . . . . . . . . . . . . . . . . ::* φm(
x) if Qm(x) is true ::* φm+1(
x) otherwise • #G: If φ satisfies the equation: :: φ(y,
x) = χ(y, NOT-φ(y; x2, ... xn ), x2, ... xn then φ is primitive recursive in χ. 'So, in a sense the knowledge of the value NOT-φ(y;
x2 to n ) of the course-of-values function is equivalent to the knowledge of the sequence of values φ(0,
x2 to n), ..., φ(y − 1,
x2 to n) of the original function." (Kleene (1952) p. 231)-->
Why general-recursive functions rather than primitive-recursive functions? Kleene et al. (cf §55 General recursive functions p. 270 in Kleene 1952) had to add a sixth recursion operator called the minimization-operator (written as μ-operator or
mu-operator) because
Ackermann (1925) produced a hugely growing function—the
Ackermann function—and
Rózsa Péter (1935) produced a general method of creating recursive functions using
Cantor's diagonal argument, neither of which could be described by the 5 primitive-recursive-function operators. With respect to the Ackermann function: : "...in a certain sense, the length of the computation
algorithm of a recursive function which is not also primitive recursive grows faster with the arguments than the value of any primitive recursive function" (Kleene (1935) reprinted p. 246 in
The Undecidable, plus footnote 13 with regards to the need for an additional operator, boldface added). a(a)+1, and thereby we see a single-variable function exists that cannot be created by primitive recursion alone. --> But the need for the mu-operator is a rarity. As indicated above by Kleene's list of common calculations, a person goes about their life happily computing primitive recursive functions without fear of encountering the monster numbers created by Ackermann's function (e.g.
super-exponentiation).
1952 "Turing's thesis" Turing's Thesis hypothesizes the computability of "all computable functions" by the Turing machine model and its equivalents. To do this in an effective manner, Kleene extended the notion of "computable" by casting the net wider—by allowing into the notion of "functions" both "total functions" and "partial functions". A
total function is one that is defined
for all natural numbers (positive integers including 0). A partial function is defined for
some natural numbers but not all—the specification of "some" has to come "up front". Thus the inclusion of "partial function" extends the notion of function to "less-perfect" functions. Total- and partial-functions may either be calculated by hand or computed by machine. : Examples: :: "Functions": include "common subtraction
m −
n" and "addition
m +
n" :: "Partial function": "Common subtraction"
m −
n is undefined when only natural numbers (positive integers and zero) are allowed as input – e.g. 6 − 7 is undefined :: Total function: "Addition"
m +
n is defined for all positive integers and zero. 1, ...,
xn of natural numbers as arguments takes at most one natural number
φ(
x1, ...,
xn) as value" (p.325). ::When an
n-tuple produces a value we say its function
φ is defined for that
n-tuple; otherwise we say
φ is undefined for that
n-tuple. : Definition: "A partial function of positive integers is one whose domain [i.e. the list of possible "input" positive integers] is something less than the whole set P [of positive integers]" (Boolos–Burgess–Jeffrey (2002) p. 7) --> We now observe Kleene's definition of "computable" in a formal sense: : Definition: "A partial function φ is
computable, if there is a machine M which computes it" (Kleene (1952) p. 360) : "Definition 2.5. An
n-ary function
f(
x1, ...,
xn) is
partially computable if there exists a Turing machine Z such that ::
f(
x1, ...,
xn) = ΨZ(
n)(
x1, ..., [
xn) : In this case we say that [machine] Z computes
f. If, in addition,
f(
x1, ...,
xn) is a total function, then it is called
computable" (Davis (1958) p. 10) Thus we have arrived at ''Turing's Thesis'': : "Every function which would naturally be regarded as computable is computable ... by one of his machines..." (Kleene (1952) p.376) Although Kleene did not give examples of "computable functions" others have. For example, Davis (1958) gives Turing tables for the Constant, Successor and Identity functions, three of the five operators of the
primitive recursive functions: : Computable by Turing machine: :: Addition (also is the Constant function if one operand is 0) :: Increment (Successor function) :: Common subtraction (defined only if
x ≥
y). Thus "
x −
y" is an example of a partially computable function. :: Proper subtraction
x┴
y (as defined above) :: The identity function: for each
i, a function UZ
n = ΨZ
n(
x1, ...,
xn) exists that plucks
xi out of the set of arguments (
x1, ...,
xn) :: Multiplication Boolos–Burgess–Jeffrey (2002) give the following as prose descriptions of Turing machines for: :: Doubling: 2
p :: Parity :: Addition :: Multiplication With regards to the
counter machine, an
abstract machine model equivalent to the Turing machine: : Examples Computable by Abacus machine (cf Boolos–Burgess–Jeffrey (2002)) :: Addition :: Multiplication :: Exponention: (a flow-chart/block diagram description of the algorithm) Demonstrations of computability by abacus machine (Boolos–Burgess–Jeffrey (2002)) and by counter machine (Minsky 1967): : The six recursive function operators: ::# Zero function ::# Successor function ::# Identity function ::# Composition function ::# Primitive recursion (induction) ::# Minimization The fact that the abacus/
counter-machine models can simulate the recursive functions provides the proof that: If a function is "machine computable" then it is "hand-calculable by partial recursion". Kleene's Theorem XXIX : : "
Theorem XXIX: "Every computable partial function φ is partial recursive..." (italics in original, p. 374). The converse appears as his Theorem XXVIII. Together these form the proof of their equivalence, Kleene's Theorem XXX.
1952 Church–Turing Thesis With his Theorem XXX Kleene
proves the
equivalence of the two "Theses"—the Church Thesis and the Turing Thesis. (Kleene can only hypothesize (conjecture) the truth of both thesis –
these he has not proven): :
THEOREM XXX: The following classes of partial functions ... have the same members: (a) the partial recursive functions, (b) the computable functions ..."(p. 376) :: Definition of "partial recursive function": "A partial function φ is partial recursive in [the partial functions] ψ1, ... ψn if there is a system of equations E which defines φ recursively from [partial functions] ψ1, ... ψn" (p. 326) Thus by Kleene's Theorem XXX: either method of making numbers from input-numbers—recursive functions calculated by hand or computated by Turing-machine or equivalent—results in an "
effectively calculable/computable function". If we accept the hypothesis that
every calculation/computation can be done by either method equivalently we have accepted both Kleene's Theorem XXX (the equivalence) and the
Church–Turing Thesis (the hypothesis of "every").
A note of dissent: "There's more to algorithm..." Blass and Gurevich (2003) The notion of separating out Church's and Turing's theses from the "Church–Turing thesis" appears not only in Kleene (1952) but in Blass-Gurevich (2003) as well. But while there are agreements, there are disagreements too: : "...we disagree with Kleene that the notion of
algorithm is that well understood. In fact the notion of algorithm is richer these days than it was in Turing's days. And there are algorithms, of modern and classical varieties, not covered directly by Turing's analysis, for example, algorithms that interact with their environments, algorithms whose inputs are abstract structures, and geometric or, more generally, non-discrete algorithms" (Blass-Gurevich (2003) p. 8, boldface added) == 1954 A. A. Markov Jr.'s characterization ==