This month’s topics:
DeepMind at the Math Olympics.
Siobhan Roberts’ article in the July 25, 2024 New York Times bore the title “Move Over, Mathematicians, Here Comes AlphaProof.” The story: two of Google’s DeepMind routines were turned loose on the six problems posed at the 2024 International Mathematics Olympiad, held in Bath, UK, July 11-22. As Roberts tells us, it took them only 19 seconds to dispatch this year’s only geometry problem, Problem 4. (Problem 4 also had correct solutions from 393 of the 609 contestants, who have 4$\frac{1}{2}$ hours to work on three problems on each of two days.)
That performance recalls news from earlier this year: in January, DeepMind announced their machines could solve past IMO geometry problems. But DeepMind also solved Problem 6, where only 5 contestants achieved a perfect score. This problem involves elementary arithmetic and complex reasoning and is, I suspect, the one Roberts mentions as having taken DeepMind three days to solve.
Roberts quotes DeepMind’s David Silver FRS (also professor at University College, London) saying that he hopes this achievement “represents the point at which we went from computers only being able to prove very, very simple things toward computers being able to prove things that humans can’t.”
The fifth busy beaver.
A Turing machine is an abstract model of the workings of a computer executing a program. The model is simple enough so that mathematicians can use it to prove theorems about computation, and powerful enough so that it can replicate any computer and any possible program. It can be used to prove, for example, that certain calculations will never end and that certain mathematical questions can never be answered.
A Turing machine itself is essentially a computer program: a finite series of instructions. The instructions refer to a finite collection of states, say $S_1, \dots, S_N$, and to an infinite tape on which the machine can move right or left, one step at a time. At each step, the machine can read a symbol (0 or 1) from the tape. Depending on that symbol and the machine’s current state, it erases the symbol and replaces it with 0 or 1, moves right (R) or left (L), and then goes to another specified state (possibly, the state it was in) or halts. A typical instruction reads: “current state, input, output, move, next state.”
For example, $S_3$, 0, 1, R, $S_5$ means: if in state $S_3$ the current position on the tape reads 0, then write 1, move one step right, and change to state $S_5$. The image below gives a graph-like representation of the Turing machine
| A, 0, 1, R, B |
| A, 1, 1, L, B |
| B, 0, 1, L, A |
| B, 1, 1, L, HALT |
and records its behavior when started in state A on a tape initially bearing all 0s.
Some simple examples of computations with Turing machines appear on the Stanford website.
A Turing machine can halt after a finite number of steps, or it can run forever, like the one-state machine
| A, 0, 0, R, A |
| A, 1, 0, R, A |
Starting with Tibor Radó in 1961, mathematicians were led to ask which $n$-state machines—HALT is not counted as a state—could execute the largest number of steps before halting, when starting with a tape containing all zeroes (a parallel competition looked for the largest number of 1s before halting). Such a machine was called an $n$-th busy beaver, and its maximum number of steps was denoted $BB(n)$. A one-state machine with the instruction A, 0, 1, R, HALT shows that $BB(1)\geq 1$; in fact, any one-state machine with A, 0, 0/1, R/L, HALT also stops after one step. Otherwise, the first instruction implemented would have to be of the form A, 0, 0/1, R/L, A, and such a machine would run forever. We can conclude that $BB(1)=1$. For two-state machines it has been proved that $BB(2)=6$; in fact, the machine in the example above is a 2-state busy beaver.
As Pascal Michel explains, $BB(2)=6$ and $BB(3)=21$ were proved in 1963. $BB(4)=107$ was proposed by Allen Brady in 1964; he proved it twenty years later. $BB(5)=47,176,870$ was proposed by Heiner Marxen and Jürgen Buntrock in 1990 and had not been proved in 2017 when Michel wrote his survey.
“Mathematicians Have Finally Found the Fifth ‘Busiest Beaver'” by Manon Bischoff in Scientific American (July 25) reports on the achievement. It situates this research in the history of modern mathematics, including Alan Turing’s Halting Problem result, which implies that $BB(n)$ is uncalculable in general. But for low values of $n$, Turing’s result makes the calculation of $BB(n)$ more interesting: how far can one go?
To calculate $BB(5)$, researchers needed to prove that Marxen and Buntrock’s 1990 candidate, the Turing machine illustrated above—let’s call it ${\bf M}$—was actually a busy beaver. This meant proving that none of the other $24^{10}$ (in one estimation) possible 5-state machines had a longer finite halting time. In Bischoff’s account, the problem seemed too big to handle until 2022, when Tristan Stérin, a graduate student at the time, started an international collective effort to attack it. The “Busy Beaver Challenge” paid off: the proof that ${\bf M}$ is indeed a busy beaver, and that $BB(5)= 47,176,870$, was published this month.
What about $BB(6)$? In 2020 it was estimated that it is bigger than $10\uparrow\uparrow 15$ (using Knuth’s $\uparrow$ notation where $10\uparrow\uparrow 3=10^{10^{10}}$). But there’s worse news. As Bischoff tells us, the relation of 6-state Turing machines to problems in number theory suspected to be unsolvable makes it possible that we will never know it exactly.
Intricate mazes on non-periodic tilings
Popular Mechanics, Science Alert, Science News and the New Scientist picked up “Hamiltonian Cycles on Ammann-Beenker Tilings” by Shobhna Singh, Jerome Lloyd and Felix Flicker, published in Physical Review X on July 10, 2024. What caught their interest was the possible interpretation of those cycles (which are intricately convoluted closed curves) as the walls of mazes. As Matthew Sparkes put it, in his New Scientist headline, “Incredibly complex mazes discovered in structure of bizarre crystals.” Sparkes is referring to quasi-crystals, some of whose planar sections can be approximated by Ammann-Beenker (AB) tilings.
AB tilings are a family of non-periodic tilings of planar regions. They have many properties in common with one version of the more famous Penrose tilings. In particular there are only two kinds of tiles, both rhombs (equilateral parallelograms) with the same side length but different angles. These tiles cannot be placed together any which way: the rhombs carry markings (“decorations”) that must match up. Here we implement them as curves on the tiles; the “matching rules” for an AB tiling state that when two tiles are adjacent, the curve ends on the shared edge must match exactly. If you just start putting tiles together you will probably soon get into a situation where there is no way to add a new tile without breaking the matching rules. The safest way to generate an arbitrarily large AB tiling is through inflation. Each tile admits an AB tiling of its own, and the matching rules guarantee that these new tilings fit together to cover the entire original region. Then rescaling the new tiles to the original size gives a tiling roughly 2.5 times the size of the one you started with. The process can then be repeated.
Singh et al. describe an algorithm for constructing a Hamiltonian cycle (a closed path that goes through every vertex exactly once) on a neighborhood of the center in the double inflation of this doubly inflated tiling. (In an earlier paper, Flicker and two other authors prove that a Penrose tiling does not admit such a path).
The Hamiltonian cycle, being a simple closed curve, must separate the plane into two connected components. So, every point not on the curve is either “outside” and can be reached by a path from the exterior, or “inside,” and cannot. Is that red dot in the center inside or outside?