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,