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