Blog

It’s happened to all of us – the computer program you’re using starts thinking and won’t respond. Sometimes, you just need to wait for it to finish what it’s doing. But other times, it’s stuck in a loop and it’ll never recover. So is it time to press the reset button?

This is a very old and famous question among computer scientists. And now, mathematicians finally have an answer! Except, only for a very simple computer.

How simple is this computer? It can’t draw pictures or write text. It can’t accept signals from a mouse or a keyboard. All you can do is turn it on and see what it does. And inside, it doesn’t have much going on.

It has some memory, which acts a bit like a strip of paper covered in ones and zeros. Each cycle, the computer looks at one of the numbers and follows a set of instructions. These instructions could tell the computer to erase the number it’s looking at and write a new number. Next, they tell the computer to go left or right to the next number on the strip. Finally, the computer is told which set of instructions to follow next.

The trick is, there are only 10 sets of instructions in the entire computer – five for when it reads a one, and five for when it reads a zero. But depending on the exact instructions, it’s very tricky to work out whether it gets stuck in a loop.

Experts started thinking about this question in the 1960s. In 1989, Heiner Marxen and Jürgen Buntrock found a set of instructions that wasn’t quite looping. It took 47,176,870 steps, writing, moving and reading until it eventually stopped. That’s a monumental length for such a simple computer!

Since then, mathematicians and computer scientists have searched for an even slower computer. They’ve analysed every possible computer with 10 sets of instructions, and it turns out that Heiner and Jürgen’s was the slowest possible. This result took years of effort from a team of experts.

So how do you work out if your (very simple) computer is looping? Wait for 47,176,870 cycles, and if it hasn’t stopped yet, it’s in a loop!