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 = [log 10 (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

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2010 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.