Computing a way through the Turing barrier

His goal – to find ways of mathematically modelling how the universe computes – is a task which increasingly engages the world’s most sophisticated logical minds. While the next generation of computers may boost the power of calculation ten or even a hundred-fold, there will still be many complex scientific questions they cannot resolve.

No one has yet managed to model computably the confusing mix of irrefutable laws and chaotic events which seem to govern nature, making, for example, weather patterns so difficult to predict. “Our notion of a mechanical universe governed by the laws of nature does not sit easily with the apparent randomness which we now know forms an important element of subatomic phenomena,” Professor Cooper said. “What I am asking is how can we make a computer model for what is happening which somehow takes account of the incomputability in nature.”

A new paradigm of computation is being sought by academics working in the field of incomputability with the aim of breaking through the ‘Turing barrier’, named after Alan Turing, the founding father of computing.

By returning to the roots of what mathematics can and cannot prove, Turing demonstrated that there are apparently some problems no present-day computer could ever solve – seemingly random events taking place in the real world which cannot be predicted. So the Turing barrier is a line in the sand, where problems are divided into those which are computable and those which aren’t, and has placed a limit on scientific work completed ever since.

Simple entities operating in an environment can form more complex behaviours as a collective, an occurrence known as ‘emergence’. A good example of this is the stock market, where the individual work of each broker combines to form the complexity of the stock market as a whole. Weather phenomena such as hurricanes are emergent properties, as is life itself. In a year which opened with such terrible scenes in south Asia, our inability to predict natural phenomena has never seemed so relevant.

Academics across Europe have been working on new models of computation for some time within their own field, coming at the subject from very different angles. To encourage collaboration and drive theories forward, Professor Cooper has formed the Computability in Europe network. Its first major event is a conference this June, bringing together mathematicians, computer scientists, physicists and philosophers with the common aim of ‘knowing the unknowable’.

“There is plenty of computability – and incomputability – theory happening, but researchers have until now tended to work in isolation,” Professor Cooper added. “I wanted to make this community of researchers a reality, where a five-minute chat over coffee could set off a whole new train of ideas.”

Professor Cooper and colleagues in the network are applying for a Marie Curie grant of around £1.75m to support Computability in Europe over the next four years. The money would be spent on finding the new computability stars of tomorrow – funding for new research students and training, as well as networking/workshops and a major conference each year.

But could the Turing barrier be eventually breached? One popular suggestion is to focus on the area of quantum computers, although these are currently more about achieving greater efficiency. Today’s computers are not far removed from Turing’s original machine of the 1930s. Although they have become faster and smaller, they still work with ‘bits’ represented as a 1 or a 0. However, research is now being conducted into new ‘quantum’ computers, which work with quantum bits represented by a 1 or a 0 , both a 1 and 0 or somewhere in between. This gives quantum computers the potential to be more powerful and millions of times faster than today’s computers.

These computers could have life-changing results. On a basic level they could be used to decode encrypted information almost instantly. Information transported over the internet could be easily manipulated by hackers able to break the encryption in seconds. More positively, they could allow us to predict the weather months in advance, by analysing its complex, seemingly random, behaviour. They could have economic applications, giving us more predictive power over the global economy. In short, they could change the world.

“The computer revolution made a huge difference to everyday life. In breaking the Turing barrier, our knowledge of the world, and therefore our control of it, would be altered forever,” Professor Cooper added.