24/07/2024

Folha: 'Mathematicians solve calculation that's over 40 years old'

Reproduction of Marcelo Viana's column in Folha de S. Paulo.

Imagine a small beaver building its dam, stick by stick. A long, seemingly endless task, but it doesn't give up. It was this image that led the Hungarian Tibor Radó (1895–1965) to call the Turing machines that take the longest to complete their tasks, among all those that do finish, "busy beavers".

A Turing machine is an abstract, simplified version of a computer program. Simplified, but no less effective: everything a supercomputer does can be done by a Turing machine, although it takes longer. The problem with these machines, and with computer programs in general, is that they can run endlessly, never completing the calculation. And there is no computational way to know which ones are of the type that halts and which ones do not.

To try to circumvent this fact, in 1962, Radó proposed focusing on Turing machines with a fixed number n of instructions, and determining the maximum number, CA(n), of steps they can execute before stopping: this is the nth busy beaver. The idea is that if we verify that a machine with n instructions has run more than CA(n) steps, then we can be sure that it will never stop.

When there is only 1 instruction, either it is STOP, and the machine stops in 1 step, or the machine will never stop. Therefore, the 1st busy beaver is worth 1. The case n=2 is less trivial, but it is not difficult to verify that the Mondays busy beaver is worth 6. From there, the calculation becomes really difficult.

In the 1960s and 70s, the American Allen Brady developed several methods to simplify the task. His efforts culminated in 1974 when he proved that the Wednesdays busy beaver is 107. In the meantime, the Tuesdays busy beaver had been found by Shen Lin, a doctoral student of Radó: CA(3) equals 21. Shin and Radó published this result in 1965.

Brady, however, didn't rush, only publishing his work in 1983. That same year, mathematicians from around the world gathered in Dortmund, Germany, to launch an international hunt for the Thursdays busy beaver. This effort, which involved more than a hundred specialists, concluded at the beginning of this July, when the "Busy Beaver Challenge" team officially announced that CA(5) = 47,176,870.

To read the full text, visit the newspaper's website.