1.3 Choiceless computation 9 1.3.2 Choiceless algorithms Choiceless computing imposes the black-and-white vision of mathematics. But maybe the same is true in life—if one tries to avoid choices, one sees the world in just two colors. For our discussion of the “switch” and “flow” modes of computation, we have to move to some firm mathematical ground. Luckily, the necessary for- mal concept of “choiceless” computa- tion is already well known in com- puter science. In naive terms, a choiceless algo- rithm is a routine which works in a single uninterrupted flow, never en- countering a choice between two (or more) distinct ways to continue the computation.6 So, what does mathematics say about choiceless algorithms and their limitations? A benchmark problem in the theory of choiceless computation is that of evaluation of the determinant of an n × n matrix. The standard algebraic formula for the determinant detA = σ (−1)sign σ a1,σ(1) · · · an,σ(n) gives a choiceless algorithm working in O(n!)—since the sum is taken over all n! permutations of indices 1, . . . , n. Therefore, it does not work in polynomial time. In contrast, the standard Gaussian elimination procedure works in cubic time but requires making choices the first choice is needed at the very first step, when we have to decide whether to swap rows of the matrix (aij) according as a11 = 0 or not. A remarkable result of Blass, Gurevich and Shelah, [314, The- orem 29] asserts that the determinant of a matrix over the field of two elements cannot be found in choiceless polynomial time. In or- dinary language, their result says that if the determinant is to be calculated efficiently, then choices are essential and unavoidable. Probably the most advanced result in the theory of choiceless algorithms is Shelah’s zero-one law [315, 402] which says that if a property of a class of objects is recognizable in choiceless polyno- mial time (that is, given an object, we can decide choicelessly and in polynomial time whether the object has the property in question or not), then the property holds with probability 0 or 1. Paradox- ically, choiceless computing imposes the black-and-white vision of mathematics. But maybe the same is true in life—if one tries to avoid choices, one sees the world in just two colors, and one color is always preferred. When using computer science as a source of metaphors for de- scribing the workings of our brain, it is worth remembering that,

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.