How Mathematical Games Save Your Life Everyday
Sven Sandberg
Computer Science
Uppsala University
October 2003
Computer programs often crash or behave incorrectly. When this
happens to your word processor, it's irritating. But it simply must
not happen to the programs used in nuclear plants, or in millions of
pacemakers, trains, or traffic lights. These errors happen because
every computer program is written by a human, and humans sometimes make
mistakes. I study mathematical methods to analyze programs. My method
is to think of the situation as a game, where the program plays against
a hostile outside world. The outside world wins if the program crashes,
so we want the program to win. The idea is to write another program that
automatically figures out if the original program has a strategy to always
win, and the big challenge is to make this method for analyzing programs
fast enough to be useful.
Out of all the computers in the world, the ones you see and use on
your desktop are only the top of an iceberg. Most computers sit
inside some machine, like your stereo or vacuum cleaner; a modern car
contains hundreds of them. Many computers do very critical tasks:
they control a nuclear plant; the brakes of a car, bus or train; or a
respirator in a hospital. It is not acceptable for such programs to
contain errors, and yet it is very difficult for humans to write
perfect programs.
Imagine you have written a program controlling the brakes of a car.
When the cars hit the road you'd better be sure there are no mistakes.
How do you know your brakecontroller works under all circumstances?
A good way is to test it under the worst imaginable circumstances.
For example, give your program the signals that the car gives when the
driver presses the brakes at high speed. This is a sort of game: you play
against the program. You win if the program crashes, and the
program wins if it is able to respond as you expect to the signals you
give it. You have to know that your brakecontroller always wins, no
matter how well you play.
In principle, you could determine who wins by trying all possible ways
to play the game. That is, you would have to think of all situations
that your brakeprogram can possibly encounter. But there are usually
so many combinations that this would take thousands of years, even if
the world's fastest supercomputer played the game for you. Sometimes
there is even an infinite number of ways to play. Therefore, the following
problem is crucial: how can we prove mathematically
that a player always wins a game, without playing all possible games?
My research area takes this one step further: I study how to write a
program that analyzes the game automatically and finds the winner. I
do not actually write the program, but I study the mathematics needed
to write it. Such a computer program can analyze the game between you
and your brakecontroller (or any other program) and say who will win,
without having to play every possible game.
Even without investigating all possible ways of playing the game, the
major problem is that the analysis is too slow. The problem of slow
analysis is so big that it does not help that computers get faster and
faster every year. So I attack it from two other and more powerful
directions. First, I try to invent more clever methods of analyzing
the games, so that the program for finding the winner can work faster.
Second, I work from the opposite direction, trying to prove that the
game cannot be analyzed quickly. Namely, a slow program is not
necessarily poorly written: it may be impossible to write a fast
program that does the same job. There are many examples of such
provably difficult problems, for which every program solving it is
slow. I want to know if finding the winner in the game is one of
them.
Our research group of three people has improved an existing method for
analyzing games, and also provided basic mathematical results useful within
the community. But the most intriguing questions remain
unanswered; the ultimate and very elusive goal is methods with speed
of a completely different magnitude than current ones.
To summarize, I use mathematics to investigate the speed of methods to
find the winner in games. The most important questions are: how can I
make the methods faster, and what is the limit for how fast they can get?
