Alan Turing at 16. Image: Turing Archive

This Turing machine should run forever, unless our understanding of maths is flawed

Time will tell.

FIONA MACDONALD
12 MAY 2016
 

Mathematicians have just designed a computer program that could prove the last 150 years of maths wrong if it ever stops running.

That's not likely to happen any time soon, but the very creation of the program is testing the limits of some of the fundamental problems upon which modern mathematics is built. It's also an incredibly cool demonstration of how a machine Alan Turing came up with in 1936 continues to push the boundaries of maths.

 

As Jacob Aron reports for New Scientist, the computer program is a simulation of something called a Turing machine, which is a mathematical model of computation developed in the '30s by Turing - the British mathematician who cracked the Enigma code during WWII, and whose life was the basis of the 2014 film, The Imitation Game.

Put simply, the Turing machine isn't a physical machine, but you can imagine it as an never-ending line of tape, broken down into squares. On each of those squares is a 1, a 0, or nothing at all. The machine reads one square at a time, and depending on what it reads, it performs an action - it either erases the number and writes a new one before moving on, or simply moves on to a different square.

Each of those actions, which mathematicians call a 'state', are determined by the mathematical algorithm or problem the Turing machine has been designed to solve. 

This is the best explanation of a Turing machine we've come across, for those who have the time to really wrap their head around the idea:

Eventually, after rewriting all the squares, a Turing machine will halt, and whatever is left on the tape is the answer to the problem, programmed in 1s and 0s. Or at least, that's what's happened for the problems we've hypothetically thrown at it so far.

 

Now, researchers Scott Aaronson and Adam Yedidia from MIT have designed three brand new Turing machines which ask three incredibly important questions in mathematics. 

And if any of them ever stops working, or 'solves' its problem, then it will suggest that a whole lot of what we know about maths wrong.

The first problem dates back to the 1930s, when mathematician Kurt Gödel demonstrated that some mathematical statements can never be proven true or false, they're simply undecidable. 

That maths is pretty complex, but as Aron explains: "He essentially created a mathematical version of the sentence 'This sentence is false': a logical brain-twister that contradicts itself."

The clause to that is that you could prove a problem decidable if you changed the basic assumptions underlying the problem - known in maths as the axioms (not to be confused with axions) - but then that would make other problems undecidable. "That means there are no axioms that let you prove everything," says Aron.

Turing took that idea and ran with it - he proposed that there must be some Turing machines whose behaviour couldn't be predicted given the standard assumptions that underpin most modern maths - known as ZMC (or Zermelo-Fraenkel set theory with the axiom of choice, if you want to get specific). Those assumptions, or axioms, are sort of what Einstein's general theory of relativity is to physics, and explain how things work in the mathematics world.

But no one had ever figured out how complex a Turing machine would need to be before it couldn't be solved - in other words, how many actions it would need before it just kept on going forever. Until now that is, because Yedidia and Aaronson claim they've created a Turing machine with 7,918 states (or actions) that should, in theory, go on forever. They named it 'Z'.

"We tried to make it concrete, and say how many states does it take before you get into this abyss of unprovability?" says Aaronson.

The Z machine is only a computer simulation for now, but it could be built into a physical device. "If one were then to turn such a physical machine on, what we believe would happen would be that it would run indefinitely," Terence Tao from the University of California, Los Angeles, who wasn't involved in the study, told Aron. (That's assuming it doesn't break or run out of power, of course).

If the Z machine did stop, it wouldn't be the end of maths as we know it - you could recreate a Turing machine with more rigid axioms, or assumptions, in place so that it would keep going. But it would show that, eventually, a Turing machine would be able to 'decide' all problems.

The other two Turing machines that Aaronson and Yedidia have designed would have bigger impacts if they stopped working. Aron explains:

"These will stop only if two famous mathematical problems, long believed to be true, are actually false. These are Goldbach’s conjecture, which states that every even whole number greater than 2 is the sum of two prime numbers, and the Riemann hypothesis, which says that all prime numbers follow a certain pattern. The latter forms the basis for parts of modern number theory, and disproving it would be a major, if unlikely, upset."

Not to be a buzz-kill here, but the mathematicians don't actually have any intention of building these machines and turning them on, primarily because it's not a very efficient way of testing problems (especially seeing as you'd have to live forever to get the results).

But the benefit of designing these Turing machines is that it helps to work out how complex these fundamental problems are. The Goldbach machine, for example, has 4,888 states, the Riemann machine has 5,372, and the ZFC one has 7,918, suggesting that final problem is the most complex - something most mathematicians would intuitively assume, Aaronson adds.

The claims surrounding these three Turing machines haven't been peer-reviewed, but the team has published their code and all their calculations online, in the hopes that other mathematicians out there will test and build upon their work and create Turing machines for these problems that are even less complex, and confound the machine with less actions.

That research could change our understanding of modern mathematics, or help reassure us that what we know so far is right. Either way, it's pretty exciting.

More From ScienceAlert