A newly proposed cosmic speed limit may constrain how fast anything in the universe can grow. Its existence follows from Alan Turing鈥檚 pioneering work on theoretical computer science, which opens the intriguing possibility that the structure of the universe is fundamentally linked to the nature of computation.
Cosmic limits aren鈥檛 a new idea. While studying the relationship between space and time, Albert Einstein showed that nothing in the universe can exceed the speed of light, as part of his special theory of relativity. Now, at the University of Oxford is proposing a new physical limit based on computation.
鈥淚 had the seed of this idea more than 20 years ago,鈥� he says. 鈥淚t would apply to any quantity you can directly measure, including mass, charge, energy, etc., and even more subtle things like the time intervals between a sequence of events.鈥�
Advertisement
While devices like smartphones and laptops grow more powerful over time thanks to technological advances, we know that there are theoretical limits to computation 鈥� in particular, that some problems are 鈥�undecidable鈥�, meaning that no algorithm can answer them, no matter how powerful the computer.
One important example of this in the history of computer science is the 鈥�halting problem鈥�, which asks whether a particular computer program will ever finish running or run forever. In the 1930s, Alan Turing and other researchers showed that the halting problem is undecidable. They used a mathematical model of computation that has since become known as the 鈥淭uring machine鈥�, and contemporary computer scientists broadly agree that if a problem is undecidable by a Turing machine, then it will also be impossible for any real, physical computer to tackle.
Ord is now proposing that the halting problem implies a physical limit for the growth of anything in the universe. To make the connection, he turned to another peculiar piece of mathematics called the Busy Beaver function, which tells you the longest time that a Turing machine can run, but still stop, depending on the number of states it has, also known as its size.
As you consider larger and larger machines, this function grows extraordinarily quickly 鈥� its first two values are 1 and 6, but its fifth value is 47,176,870. The next value to exceed a number so staggeringly large that it is difficult to express in standard mathematical notation. Written 10鈬�15, it is 10 raised to the power of 10 repeatedly to create a 鈥減ower tower鈥� of 15 10s.
Because of its definition, any physical process that grows faster than the Busy Beaver function could be used to compute the halting function, which researchers think is impossible. Ord realised that this impossibility may be a two-way street.
鈥淚 turned this around, noticing that if the Turing machine really is the limit on what is computable in our universe, there must be no directly measurable quantities that grow this fast,鈥� he says. In other words, the Busy Beaver function just may be the ultimate cosmic limit on how fast any physical process or system can grow 鈥� because a physical process that grows faster could be used to solve the halting problem, which ought to be incomputable.
Ord鈥檚 limit wouldn鈥檛 just apply to very fast-growing processes, but also very slow ones, using what Ord calls the Sleepy Sloth function. Specifically, this slowness is tied to Busy Beaver鈥檚 values, so Sleepy Sloth starts at 1 and only reaches 5 as its 47,176,870th value.
鈥淚t is somewhat intuitive that there is an upper limit to how quickly things can grow, but surprising that there is also a limit on how slowly they can grow,鈥� says Ord. It is unlikely that anything in the universe would actually brush against either of these limits, but he says that it is a situation similar to the speed of light, where the fact that a limit exists at all may reflect something fundamental about the universe.
at the University of Texas at Austin says that while computer scientists have long been interested in theoretical implications of the Busy Beaver function, Ord鈥檚 work demonstrates how it may also connect to the physical world.
at Swansea University in the UK says that one difficulty with the new argument may lie in how we would measure and characterise a physical process that grew faster than Busy Beaver, given its incomputability. That means there could be something that breaks Ord鈥檚 proposed cosmic limit, but we would struggle to recognise it as doing so. 鈥淚 think there still is a hope of breaking this speed limit, but we would need to have some physical phenomenon that we knew about and that we actually knew could give us that boost,鈥� says Beggs.
Even if Ord is ultimately proved wrong, the connections between the physical world and Turing鈥檚 ideas have been puzzling researchers for almost a century, and will continue to do so, says , also at Swansea University. 鈥淭he mathematics is sufficiently intriguing to warrant an enormous effort to keep pounding away at different perspectives,鈥� he says.
For Ord, one of those perspectives may even be pushing back on the idea of limits of computability themselves. Ideas about Turing machines have been taken as settled for decades, but they are still mostly very strong hypotheses rather than irrevocably proven facts. If their repercussions are as dramatic as introducing new limits on physical reality, this raises the stakes on re-examining them and proving them more rigorously 鈥� lest we misunderstand the cosmos at large. 鈥淭hey may be less innocuous than we鈥檇 thought,鈥� says Ord.
arXiv
