|
Chapter 5 Mathematical Recursion |
|
Mathematical recursion is the theoretical rootstock of applied computation.
Recursion has grown from antiquity's bud into a stout, corkscrewed trunk — fruitful in application, of course. Brief examples
will slice open the corkscrewed trunk at points of interest.
Exponentiation provides our first example:
it's a quick mathematical recursion. I'll follow with mechanical and biological examples which penetrate Proclus' metaphysics (and a great
many others).  But starting near the root, with exponentiation. How is it done? Oftentimes we use an intuitive method. If we want
to calculate the exponent, 23, "off
the cuff," we might calculate it this way:
Here we've used an intuitive, informal definition of
exponentiation. This definition is not recursive. A recursive definition calculates the exponent
in a different way. Such a definition has two
parts: a base clause and a recursion clause.[1]
A recursive definition of exponentiation takes this form:
[Note that the recursion clause
refers to itself, in the sense that higher terms (j+1) are defined with reference to lower terms (j). For this reason the clause can be invoked
repeatedly during calculation. (It can recur many times.)
This behavior is shown below.]
The
definition is concise — but how to apply it? We have no rule. A mathematician must exercise judgment in
interpreting the definition, before using it to calculate an actual
exponent. We might interpret the recursive definition of exponentiation so
as to calculate 23 this way:
The definition doesn't say, explicitly, that it must be used in just this
way. Again, it's the human mathematician who provides the interpretation,
and then the driving force, to perform the math. The mathematician is the
motive "cause," after Proclus.
Can recursive definitions be
modified so as to acquire
self-motive power? Well, a more modern form of recursion is found in the
recursive function. A recursive
function, like a recursive definition, also has a base clause. The
difference is that rather than having a recursion clause, it has a recursion formula.
Also there is a strict rule for use of the formula.
Here is
exponentiation with a recursive function:[2]
[The variable m stands for
the base term to be exponentiated. (In this example, it is "2".) The variable
n stands for an exponent in
the natural number sequence
0, 1, 2, 3, .... The prime symbol (
' ) means
"plus 1." So the natural number sequence is formally stated as
0, 0', 0'',
0''', .... Hence the use of
n
and
n'
in the
formula.]
The rule for use
of the formula is simple: we apply the formula repeatedly until the base
clause appears; then we substitute the base clause value to produce a
result.
The calculation of 23 now proceeds entirely
by rote:
This last calculation seems more "mechanical," when compared
against the other two techniques. It is indeed more mechanical, in the
sense that there is no ambiguity in the calculation. The rule is
exact. Its execution can be driven by a machine, free of human supervision. A computer can
execute the recursive function for exponentiation autonomously and thereby
mechanically calculate any exponent.
By this technique recursion has
acquired self-motive power. Computers execute recursive functions every
day. (The web browser displaying this very page is itself an amalgam of
recursive functions.)[3]
To begin with,
we note that our exponentiation function is an example drawn from that class of recursive functions called "partial recursive
functions."[4] An
important property of any partial recursive function is that its value can
be obtained by a finite number of steps. Hence its value can be
computed in a finite amount of time. Or saying it another way, its value
can be "effectively" computed.
Partial
recursive functions have been proved equivalent to those functions computable on
abstract Turing machines.[5] This proof applies to all digital computers, as they are
logically equivalent to Turing machines in their operation.[6]
So digital computers can compute all partial recursive functions. Alonzo Church
and Alan Turing took this proved result a step farther by proposing two
stronger, and similar, theses. They proposed:
These two theses are interchangeable, and
are sometimes spoken of jointly as the "Church-Turing Thesis,"[9] which I'll abbreviate as CT.
If correct, CT
would prove directly that no upper limit exists on the computational power of
recursive functions as implemented on digital computers.
Has CT been proved? Here it would be appropriate to
let mathematicians speak for themselves, voicing their professional opinions on
the proposed proofs and refutations of CT:
The opinions are diverse because CT is not really a mathematical theorem. The
converse of C and T have been proved mathematically true, but CT itself argues for something rather more philosophical; namely, the
true nature of computation. As an empirical fact, CT has been applied successfully to all known classes of computable functions. So it remains a useful "working theory" of
computability. On balance, the
quotations above seem to weigh in favor of
CT, and against Proclus; but they
also suggest that the ultimate validation of CT will be experimental. The experiments of most interest, and of
greatest relevance to Proclus' argument, are those which have the human body
as their subject of study.
In the next
chapter we will study a prime example of recursive computation in the
human body.
next Chapter 6: Episodic Memory |
|
Chapter 5 Endnotes |
|
[1] Defined after Browski, E. J. and J. M. Borwein, eds., Dictionary of Mathematics,
s. v. "Recursive Definition"
(London: Collins, 1989). See also: Encyclopaedia Britannica article on recursive definitions.
[2] Defined after Judson Chambers Webb,
Mechanism, Mentalism, and Metamathematics (Dordrecht: D. Reidel Publishing,
1980) 51.
[3] For an overview of computable functions, see I. A. Lavrov and A.
D. Taimanov, "Computable Function,"
Encyclopaedia of Mathematics (Dordrecht: Kluwer Academic Publishers,
1980). For a full definition of primitive recursive functions, see Stephen
C. Kleene, Introduction to Metamathematics
(Princeton: D. Van Nostrand, 1952) 217-20.
[4] Lavrov and Taimanov, "Computable Function" 286-87.
[5] Kleene gives a formal statement of equivalence. See
Kleene, Introduction to Metamathematics
363-76, Theorems XXVIII-XXX.
[6] A good overview of Turing's analysis can be found in Stephen C.
Kleene, "Turing's Analysis of Computability, and Major Applications of
It," The Universal Turing Machine: A Half-Century
Survey 3-54.
[7] Lavrov and Taimanov, "Computable Function" 287.
[8] Webb 8. [9] For a good development of the joint Church-Turing Thesis, see
Stephen C. Kleene,
Mathematical Logic, New York:
John Wiley & Sons, 1967) 232-47.
[10] Lavrov and Taimanov, "Computable Function" 287.
[11] Robert Rosen, "Effective Processes and Natural Law,"
The Universal Turing Machine: A Half-Century
Survey 534.
[12] Michael A. Arbib,
Brains, Machines and
Mathematics, 2nd ed. (New York:
Springer-Verlag, 1987).
[13] S. G. Shanker, "Wittgenstein versus Turing on the Nature of
Church's Thesis,"
Notre Dame Journal of Formal
Logic 28.4 (1987): 643. [14] R. J. Nelson, "Church's Thesis and Cognitive Science,"
Notre Dame Journal of Formal Logic 28.4 (1987):
581-82.
|
Copyright © 1999
Wayne Stewart
Last update 4/19/11