HE CALLED it the āoracleā. But in his PhD thesis of 1938, Alan Turing specified no further what shape it might take. Perhaps that is fair enough: aged just 26, the British mathematician had already lit the fuse of a revolution. His blueprint for a universal computing machine, published two years earlier, set the specs for every computer that followed, from the humblest pocket calculator to the mightiest supercomputer ā via laptop, smartphone and all points in between.
So absorbed have we been in exploring this rich and varied legacy, and transforming our world with the machines and applications that built upon it, that we have rather overlooked the oracle. Turing had shown with his universal machine that any regular computer would have inescapable limitations. With the oracle, he showed how you might smash through them.
In his short life, Turing never tried to turn the oracle into reality. Perhaps with good reason: most computer scientists believe anything approximating an oracle machine would soon fall foul of fundamental restrictions on how information and energy flow in the universe. You could never actually make one.
Advertisement
In a laboratory in Springfield, Missouri, two researchers are now seeking to prove the sceptics wrong. Building on theoretical and experimental advances of the past two decades, and Steven Younger of Missouri State University think a āsuper-Turingā computer is within our grasp. With it, they hope, could come insights not just into the limits of computation in the cosmos, but into the most intriguingly powerful computer we know of within it: the human brain.
Computers as we know them are in essence very capable, rigorous and efficient renderings of what we humans might be capable of given precise instructions, a high boredom threshold and a limitless supply of paper and pencils. They excel at successive additions, multiplications, logical decisions, if x then y, that sort of thing. Indeed, the first ācomputersā were young researchers employed by astronomers for the tedious and time-consuming task of working out the orbits of comets or calculating the brightness cycles of variable stars.
āNormal computers can only do what we might, given a high boredom threshold and limitless paper and pencilsā
A universal computing machine ā often known simply as a Turing machine ā does the same things, only without the tedium. āElectronic computers are intended to carry out any definite rule-of-thumb process which could have been done by a human operator working in a disciplined but unintelligent manner,ā as Turing himself wrote in the for the University of Manchesterās Mark II computer in 1950.
So computers have their blind spots just as we do. No matter how disciplined, well-schooled or patient we are, certain questions defy our logic. What is the truth of the statement, āThis statement is falseā? You can spend a lifetime grumbling over the answer as many a philosopher has. In 1931, the mathematician Kurt Gƶdel demonstrated that this problem was universal with his infamous incompleteness theorems, showing that any system of logical axioms would always contain such unprovable statements.
Similarly, as Turing showed, a universal computer built on logic alone always encounters āundecidableā problems that never yield straight answers, no matter how much processor power you throw at them. One example is the halting problem. A computer can never tell if any program will run to the end, or get stuck in some infinite loop or at some instruction, without trying out the program first ā and possibly getting stuck. The āblue screen of deathā feared by many a PC user is just one consequence of this fundamental undecidability.
āA computer built on logic alone will always encounter problems it canāt answerā
An oracle as Turing envisaged it was essentially a black box whose unspecified contents would be able to solve undecidable problems. An āO-machineā, he proposed, would exploit whatever was in this black box to go beyond the bounds of conventional human logic ā and so surpass the abilities of every computer ever built.
That is as far as he went in 1938. āTuring realised that models for more powerful computing machines may exist,ā says Younger. āBut he did not present any super-Turing computational models.ā
Two decades ago, Hava Siegelmann came up with one by accident. In the early 1990s, she was working on her PhD in computer science at Rutgers University in Piscataway, New Jersey, just a 40-minute drive from Princeton, where Turing had presented his thesis. Her subject was neural networks, circuits designed to mimic the human brain and the myriad neurons connected by synapses that realise its unparalleled computing power. In a neural net, many simple processors are wired together so that the output of one can act as the input of others. These inputs are weighted to have more or less influence, and the idea is that the network ātalksā to itself, using its outputs to alter its input weightings until it is performing its task optimally ā in effect, learning as it goes along, just as the brain does. Neural nets have scored some notable successes performing tasks that cannot easily be reduced to a set of straightforward instructions, from reading medical scans and diagnosing illnesses to driving cars.
Siegelmannās initial aim was to prove theoretically the limits of neural networks: to show that, for all their flexibility, they could never have the full logical capabilities of a conventional Turing machine. She failed time and again. Eventually, she proved the reverse. One of the hallmarks of a Turing machine is that it is incapable of generating true randomness. By weighting a network with the infinite, non-repeating number strings of irrational numbers such as pi, Siegelmann showed you could, in theory, make it super-Turing. In 1993, she even showed how such a network could solve the halting problem.
Her fellow computer scientists met the idea with coolness, and in some cases downright hostility. Various ideas had been floated for āhypercomputersā that might exploit exotic physics to go super-Turing, but they always seemed to lie on a scale from implausible to utterly wacky (see āTo infinity and beyondā). Siegelmann eventually published her proof in 1995 (), but she soon lost interest, too. āI believed it was mathematics only, and I wanted to do something practical,ā she says. āI turned down giving any more talks on super-Turing computation. I told everyone, āIām out of this field nowā.ā
Redd and Younger had been aware of Siegelmannās work for a decade before they realised that their own research was heading in the same direction. In 2010, they were building neural networks using analogue inputs that, unlike the conventional digital code of 0 (current on) and 1 (current off), can take a whole range of values between fully off and fully on. There was more than a whiff of Siegelmannās endless irrational numbers in there. āThere is an infinite number of numbers between 0 and 1,ā says Redd.
Powered by chaos
In 2011 they approached Siegelmann, by then at the University of Massachusetts in Amherst, to see if she might be interested in a collaboration. She said yes. As it happened, she had recently started thinking about the problem again, and was beginning to see how irrational-number weightings werenāt the only game in town. Anything that introduced a similar element of randomness or unpredictability might do the trick, too. āHaving irrational numbers is only one way to get super-Turing power,ā she says.
The route the trio chose was chaos. A chaotic system is one whose response is very sensitive to small changes in its initial conditions. Wire up an analogue neural net in the right way, and tiny gradations in its outputs can be used to create bigger changes at the inputs, which in turn feed back to cause bigger or smaller changes, and so on. In effect, the system becomes driven by an unpredictable, infinitely variable noise.
The researchers are working on two small prototype chaotic machines that they hope to have up and running by the end of the year. One is a neural network based on standard electronic components, with three āneuronsā in the form of integrated circuit chips and 11 synaptic connections on a circuit board a little larger than a hardback book. The other, with 11 neurons and around 3600 synapses, uses lasers, mirrors, lenses and photon detectors to encode its information in light.
If only on a small scale that should be enough, the team thinks, to take them beyond Turing computation. It is a claim that invites plenty of scepticism. of the Massachusetts Institute of Technology voices the concern that mathematical models involving any sort of infinity always run into problems when they are forced to deal with reality. āPeople ignore the fact that the physical system cannot implement the idea with perfect precision,ā he says. JĆ©rĆ©mie Cabessa of the University of Lausanne, Switzerland, who used to work with Siegelmann, is similarly doubtful about super-Turing machines in practice. āTo me at the moment they are unbuildable,ā he says. Again, itās not that the maths doesnāt work ā it is just a moot point whether true randomness is something we can harness, or whether it even exists. āDoes nature achieve some intrinsic randomness? If so, perhaps there really is some super-Turing ability in nature,ā he says.
That question was clearly on Turingās mind: he often speculated about a connection between intrinsic randomness and the origin of creative intelligence. In 1947, he went so far as to suggest to his astounded bosses at the UK National Physical Laboratory near London that they should put radioactive radium into the Automatic Computing Engine he had devised, in the hope that its seemingly random decays would give its inputs the desired unpredictability. āI donāt think he intended to build the oracle machine,ā says Siegelmann. āWhat he had in mind was to build something thatās more like the brain.ā
āTuring speculated about a connection between randomness and creative intelligenceā
Since then, building a computer with brain-like qualities has been a perennial aim, with the latest large-scale initiative being part of the based at the Swiss Federal Polytechnic School in Lausanne. These endeavours, though, are all about building replica neurons with standard, digital Turing machine technology. Younger is convinced the less-rigid approach of their chaotic neural networks is more likely to bear fruit. āApplying this might take us towards brain-like intelligence,ā he says.
Hypercomputer hype
Younger and Redd are aware they are shooting for the moon. Even if their machine works significantly differently from a standard computer, proving that this is due to super-Turing computation will be pretty tough. At he moment, their best idea lies in a side-by-side comparison of the output of their machine and a standard computer, given the same inputs. A super-Turing machine can, in theory, produce outputs identical to those of chaotic systems, but a standard Turing machine will always start rounding them.
They are also hoping they will be able to recruit some assistance for testing their computers when they present their idea at a at the University of Western Ontario in London, Canada, this week. āWe will announce we donāt know how to do this, and maybe people will start thinking about it,ā Redd says.
It is a low-key kind of statement for what could be the start of computingās first real reboot. But then there has always been a lot of hype about what hypercomputers might do if they were ever to get off the ground ā for example, breaking through the boundaries of conventional computation might give us a new hold on other things that currently befuddle human logic, such as quantum theory.
Most of us would be happy if an oracle would just put an end to the blue screen of death and its equivalents. While promising nothing specific of the first trials, Redd is bullish about the outcome. āIām actually kind of confident weāll see something significant,ā he says.
Leader āWhat will hypercomputers let us do? Good questionā
To infinity and beyond
We live in a universe of almost infinite possibilities. Over the years, quite a few have been harnessed in the quest for super-powerful computers that break the limits set by Alan Turing 75 years ago.
One possibility is to create a machine that accelerates its operations, performing each successive instruction in half the time of the previous one. Given infinite iterations, such a machine will perform an infinite number of operations within a finite time. One insouciant suggestion back in 2001 was that such a trick might be made feasible .
Even further back, Mike Stannett of the University of Sheffield, UK, proposed something similar using the fact that the electron on a hydrogen atom can, in principle, . This is different from quantum computing, which exploits the āsuperpositionā of a few quantum states at any one time. A quantum computer can only do what a standard Turing machine does, albeit a lot faster.
Computers that harness the universeās fundamental processes to go super-Turing are generally referred to as hypercomputers. Scott Aaronson of the Massachusetts Institute of Technology is pretty convinced they are not a realistic prospect. He points out that schemes involving things like getting closer and closer to the event horizon of a black hole provoke reactions to stop you. āItās a cute idea, but you can calculate that the energy to do it would be so large it would warp the geometry of space-time rather than doing what you wanted,ā he says. Whatās more, the screwball rules of relativity mean you might have your computer do an infinite amount of computation in a finite amount of time as perceived by someone else ā which isnāt particularly helpful.
For Hava Siegelmann of the University of Massachusetts in Amherst, such hypercomputers are āphilosophically interestingā, but not comparable to her current project to implement a super-Turing computer (see main story). āWeāre not doing anything like that. Our design is built on Turing, with very careful and particular thought about how to do it,ā she says. āI like the hypercomputation theories as a game, but I would never think of them as actually computing.ā
This article appeared in print under the headline āKnow it allā
