1.3 Choiceless computation 7
I claim that the difference between the “switch” and “flow”
modes of computation is felt and recognized by almost every math-
ematician. Most undergraduate students of mathematics in their
second or third year of study can judge—and with a surprising
degree of certainty and immediacy in their answers—what kind
of mathematics is more suitable for them, discrete or continuous.
They just know, even if they have never before given any thought to
the issue. Perhaps, we should tell them that there is a difference.3
Not being a professional neurophysiologist, I can only conjec-
ture that the two types of mathematical activities should be re-
flected in two different patterns of brain activity, perhaps even eas-
ily noticeable with the help of modern brain scan techniques. Mean-
while, within mathematics itself the two modes of calculation are
recognized as being intrinsically different and are analyzed to con-
siderable depth. In the next section I briefly describe the findings
of mathematicians.
1.3 Choiceless computation
We choose our joys and sorrows long before we experience them.
Kahlil Gibran
So, we started with the absolute value function y = |x| as an
example of “the simplest possible example” and are now moving to
a mathematical description of the difference between the “switch”
and “flow” modes of computation.
As I will frequently do in this book, I use a concept from com-
puter science as a pointer to possible structures of human cognition
responsible for particular ways of manipulating mathematical ob-
jects. In this case, a possible indicator is the concept of choiceless
polynomial time computation [313].
Some terminology ought to be explained.
1.3.1 Polynomial time complexity
An algorithm is said to have polynomial time complexity (of de-
gree d) if, when working with inputs of size l, it requires O(ld) el-
ementary operations (see the endnote 4 for an explanation of O( )-
notation). Let us look, for example, at the addition of two integers.
The input size here is the number of digits required to write the in-
tegers down; if both summands are smaller than n, then each needs
at most
l = [log10(n)] + 1
digits (here, [log10(n)] denotes log10(n) rounded down to the near-
est integer). To add the integers, we need, in each position, to add
Previous Page Next Page