Saturday, January 23, 2021

Very slow computer programs reveal fundamental limits of mathematics

Must read

Programmers normally want to minimize their code execution time. But in 1962, the Hungarian mathematician Tibor Radó posed the opposite problem. He asked: How long can a simple computer program possibly run before terminating? Radó has dubbed these maximally ineffective but still functional programs “busy beavers”.

Original story reprinted with permission from Quanta Magazine, an independent editorial publication of Simons Foundation whose mission is to improve public understanding of science by covering developments and research trends in mathematics and the physical and life sciences.

Finding these programs has been a devilishly entertaining puzzle for programmers and other math enthusiasts since it was popularized in American scientistof “Computer leisure” column in 1984. But in recent years the beaver game, as it is called, has become an object of study in its own right, as it has made it possible to establish links with some of the most noble concepts and open problems in mathematics.

“In math, there is a very permeable line between what is a fun recreation and what is actually important,” said Scott Aaronson, a theoretical computer scientist at the University of Texas at Austin, who recently published a survey progress in “BusyBeaverology”.

Recent work suggests that researching long-lasting computer programs can shed light on the state of mathematical knowledge, and even tell us what is knowable. The heavily loaded beaver game, the researchers say, provides a concrete benchmark for assessing the difficulty of certain problems, such as the unresolved Goldbach conjecture and the Riemann hypothesis. It even offers insight into where the underlying logical foundation of mathematics breaks down. Logician Kurt Gödel proved the existence of such a mathematical terra incognita almost a century ago. But the beaver’s animated game can show where it actually stands on a number line, like an old map depicting the edge of the world.

An uncalculable computer game

The Busy Beaver Game is about the behavior of Turing machines – primitive and idealized computers designed by Alan Turing in 1936. A Turing machine performs actions on an endless strip of ribbon divided into squares. It does so according to a list of rules. The first rule could say:

If the square contains a 0, replace it with a 1, move one square to the right and see rule 2. If the square contains a 1, leave the 1, move one square towards the left and see rule 3.

Each ruler has this style of choice of adventure. Some rules say go back to previous rules; finally, there is a rule containing an instruction to “stop”. Turing proved that this type of simple computer is capable of performing all the calculations possible, with the right instructions and enough time.

As Turing noted in 1936, in order to calculate something, a Turing machine must ultimately stop – it cannot be trapped in an infinite loop. But he also proved that there was no reliable, repeatable method of distinguishing machines that shut down from machines that just run forever – a fact known as the shutdown problem.

The Charged Beaver game asks: Given a number of rules, what is the maximum number of steps a Turing machine can take before stopping?

For example, if you are only allowed one rule and you want to make sure that the Turing machine stops, you are required to include the stop instruction immediately. The busy beaver number of a single rule machine, or BB (1), is therefore 1.

But adding a few more rules instantly explodes the number of machines to consider. Of 6,561 possible machines with two rules, the one that performs the longest – six steps – before stopping is the busy beaver. But some others just work forever. None of these are the busy beaver, but how do you rule them out for good? Turing proved that there is no way to automatically tell whether a machine that runs for a thousand or a million steps will not end up stopping.

This is why it is so difficult to find busy beavers. There is no general approach to identifying the oldest Turing machines with an arbitrary number of instructions; you have to understand the specifics of each case by itself. In other words, the busy beaver’s game is, in general, “non-calculable”.

- Advertisement -

More articles


Please enter your comment!
Please enter your name here

- Advertisement -

Latest article