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,
Previous Page Next Page