91av

Santa Fe, New Mexico

THE computing revolution began in the early afternoon of a lazy English summer day in 1935 when Alan Turing, an undergraduate at King’s College, Cambridge, had an idea for an incredible theoretical gadget. Turing believed that his imaginary gadget-known today as a “Turing machine”-could carry out any process that might conceivably be called a “computation”. In effect, the machine gave mathematical substance to the informal notion of what it means to “compute.” It was an ingenious invention, and only ten years later, following the Second World War, it was with Turing’s machine firmly in mind that teams of scientists in the US and Britain- including Turing himself-built the first general purpose computing machines.

Turing’s ideas were so profound that they still dominate our conception of computing today. Every PC, microprocessor or supercomputer in the world works on the principles of Turing’s machine. And yet recently, scientists have begun to think again about the notion of computation, and to wonder if Turing’s model really exhausts the possibilities of what computing devices can be like.

What they have found is that the notion of computing might be a bit more slippery than Turing had imagined. It may soon be possible to make computers of a type never envisioned by Turing, that would be capable of computational acts that conventional computers cannot even dream of.

In everyday life, it’s common to talk about doing a “computation”. For example, we often speak informally of balancing a cheque book, computing the number of kilometres per litre of petrol obtained by our car, or converting US dollars into Japanese yen. Each of these tasks involves processing numbers in a particular way to obtain a desired result. These processing procedures are more formally called “algorithms”.

The problem faced by theoreticians is how to convert this familiar idea of computation into a precise, mathematical structure-or model-that they can use to prove things about the properties of algorithms.

Turing’s model-his “machine”-is rather abstract, and yet simple in principle. It consists of an infinitely long tape labelled with a string of 0s and 1s, together with a scanner that can be in any of several different internal states. The position of a pointer located on the scanner indicates its state. A computation is performed on the input data, initially written on the tape. The scanner moves along the tape, bit by bit, doing various simple operations depending on the pointer setting and the number it encounters on the tape. It might print a 0 or 1, move to the left or right by one bit, change its pointer setting, or stop processing altogether. When it stops, the input data has been processed to give the computational result-a tape with a new sequence of 0s and 1s.

This may seem like a crazy device. But Turing proved mathematically that a version of this computer, a “universal” Turing machine, can emulate the action of any other Turing machine. This includes any modern digital computer. So Turing’s universal machine, despite its seemingly awkward design, is in fact an exceedingly versatile device.

The notion of a Turing machine finally put the idea of computation on a solid mathematical footing. And Turing’s work, along with that of the American logician Alonzo Church, established for computer scientists an attitude regarding what is possible as far as computation is concerned. This attitude is stated in what has come to be called the Turing-Church Thesis: “A Turing machine running a suitable program can carry out any process that can reasonably be called a computation.”

The Turing-Church “thesis” is not a theorem because it’s not really amenable to proof. It’s more of a proposal, suggesting that we agree to equate our informal idea of computation with Turing’s formal mathematical idea. For the past forty years, scientists have gone along with this, and discussions in computer science departments have mainly turned on what problems can and cannot be solved by computation, and about how to rank problems by difficulty. A popular ranking puts every problem into one of three classes: easy, hard or uncomputable, according to how hard a Turing machine has to struggle to solve it.

Here is an example of a “hard” problem. Imagine a handful of popular pubs that are connected by a network of one-way roads. The puzzle is to determine if it is possible, by driving, to visit every pub once and only once.

Having chosen a possible route, it is easy to check to see whether it is indeed a solution. But it’s very difficult to find a workable route in the first place. The typical number of paths that need to be checked before one finds a solution grows exponentially with the number of pubs. This rapid growth in computational burden is shared by all hard problems, and it means that any real Turing-style machine trying to solve problems of increasing size is quickly overwhelmed by the magnitude of the task. In the pub-visiting problem, for example, the computer simply cannot check all the many possible routes in a reasonable amount of time.

Other problems aren’t so hard. For example, sorting a list of names into alphabetical order is an easy problem. To sort a longer list would take more time, certainly, but it turns out that for this, or any other easy problem, the computation time grows only as the size of the problem raised to some power. This kind of growth is much slower than exponential, so computers fare much better with these “easy” problems.

And then there are the many problems that a Turing machine simply cannot cope with at all. For example, there is no computational procedure for deciding whether it is possible to use a given set of polygonal shapes to “tile” an infinite plane with no overlaps or gaps (see diagram, p 32). Unleash a Turing machine on such a problem, and it might just run on forever without coming to a conclusion.

Instruments of the impossible

But, of course, all this reckoning of “easy”, “hard” and “uncomputable” holds only within the framework of Turing’s model. In the past few years, mathematicians and scientists have suddenly woken up to the fact that the Turing-Church thesis isn’t beyond doubt, and have begun to explore the world of exotic computing machines that fall outside Turing’s conception. Each alternative device of this sort also divides problems according to the difficulty it would face in solving them, but in principle, some machines might make easy work of some problems that are hard for a Turing machine. Better yet, it might be possible to make a device that could literally compute the uncomputable.

One alternative model is based on the notion of a cellular automaton. Imagine a chessboard where each square can have one of several different colours. If each colour corresponds to a number, then the grid holds a set of numbers, and the device processes these in a series of steps. At each step, the colour of each square on the board changes, and how it changes depends on its previous colour as well as on the colours of several other squares that are assigned to it as inputs.

These input squares may be nearby or far away. The computer runs along changing its colours until finally it stops, having changed the initial pattern of colours into a final pattern. Like a Turing machine, the device has processed the initial input data into final output data-the computational result.

Cellular automata naturally do several computational steps in parallel. Whereas a Turing machine generates a single 0 or 1 at each step, cellular automata generate many. So a computer of this type processes information more quickly. Even so, mathematicians have spoiled the show by proving that cellular automata still categorise problems into “easy”, “hard” and “uncomputable” in just the same way as Turing machines. So, while cellular automata have their advantages, these are tiny compared with what might result from a true non-Turing machine.

But two other peculiar machines, rudimentary examples of which have already been built, can compute in such a way that some hard problems really do become easy ones.

In 1994, Leonard Adelman of the University of Southern California made a computer out of DNA-the molecule of life-that can solve the hard, pub-visiting problem. His idea is to represent each pub and street by a specific DNA molecule with a unique sequence of base pairs. These sequences are designed so that a DNA molecule corresponding to a pub will link up only with molecules corresponding to a street that leads to or away from it.

Chains of thought

Adelman puts the molecules in a test tube, and waits for them to link up to form chains. The sequence of DNA molecules in each chain represents an ordering of the type “street-pub-street-pub” and so on, that is, a path. And because of the huge number of DNA molecules in the test tube, at least one of the resulting chains is highly likely to form the path that solves the problem.

In effect, this “DNA computer” makes all possible chains, and so, checks all possible paths at once. It’s as if an army of Turing machines were all working together. The real power of the scheme is most evident when the number of pubs is large, when a DNA computer would do in hours what would take a conventional supercomputer many years. It’s worth mentioning, however, that estimates suggest that it would take a biomass the size of the Earth to solve a 100-pub problem. So with DNA computing, massive parallel computation and the resulting incredible speed is achieved only with a physically huge computer.

This idea of parallel processing also underlies another model of computation. In 1982, Richard Feynman published an article entitled “Simulating Physics with Computers” in which he suggested harnessing the weird behaviour of quantum particles to compute at a pace that would far exceed the fastest possible conventional computer.

A quantum system can be in a “superposition” of more than one state at a time. For instance, the spin of an electron can be in both the up and down states simultaneously. If we represent these two states by 0 and 1, respectively, then calculations on the superposition act on both values at once.

But superpositions can be much more complex. An array of, say, 32 electrons-acting as a set of computer bits-can be in a superposition that involves literally billions of states. This allows billions of calculations to take place simultaneously, a degree of parallelism that is inconceivable for everyday computers.

In 1992, Peter Shor of AT&T Bell Labs discovered an algorithm by which a quantum machine could determine the prime factors of large numbers. Factoring is a hard problem for ordinary computers using known algorithms, because the solution time increases exponentially with the number of digits in the number to be factored. With Shor’s quantum algorithm, however, the time needed grows only as the square of the number of digits. This offers a fantastic reduction in processing time over conventional methods when the number is large. So, like a DNA computer, a quantum computer can turn some hard problems into easy problems.

So it seems that Turing was mistaken in believing that his model captured the essence of all possible computation. These alternatives seem to suggest a general recipe for making machines that go “beyond Turing”. David Deutsch of Oxford University, a theoretical physicist who works on quantum computing, points out that computer scientists since Turing had assumed that mathematics alone was sufficient to understand computation, and that physics could safely be ignored.

But as the recent discoveries show, by modifying the physical basis of computing devices, novel machines become possible. “What computers can and cannot compute is determined by the laws of physics,” says Deutch, “not by pure mathematics”. The DNA computer achieves great power by growing in physical size, and the quantum computer does the same by exploiting the propensity of quantum objects to split their existences. Perhaps other physical modifications of the hardware of computers could allow devices that can truly compute the uncomputable?

No one really knows yet. There are already a few theoretical models that may do the trick. The question is whether they are models of machines that can actually exist in this Universe.

One such model was dreamt up a few years ago by mathematician Steven Smale and computer scientist Lenore Blum of the University of California at Berkeley, along with mathematician Michael Shub of the IBM Research Division. They were interested in the fact that scientists quite commonly have to deal with computational problems that involve real numbers-like the square root of 2, or 4/3-rather than whole numbers. The Turing machine model isn’t well-suited to tasks of this sort, defined as it is in terms of strings of 0s and 1s. So the trio developed a new model (named for them as the BSS model) that accommodates both whole and real numbers. The trick is to slip inside the machine a new processing element that can carry out the most basic real number operations, such as division, with perfect accuracy.

If one assumes that this can be done, then the BSS model can compute things that Turing’s machine cannot. For example, it could calculate the cube root of 3, and give the result with perfect accuracy. A Turing machine could never do that. Still, no one yet knows how you might build such a machine. The problem is how to realise in a physical device the essential “real number” processing element that is the secret of the BSS model. So for now this model remains in the realm of the imagination.

But if what is computationally possible is, in fact, closely bound up with what is physically possible, then this raises an intriguing question: Is there any physical process, following the known laws of physics, that is itself uncomputable? Does anything in the Universe act in such a way that its behaviour cannot even in principle be simulated by a Turing machine? If such a process could be found, then building a computational device on its back would be a sure way to make a device that could compute the uncomputable.

In recent years, the physicist Roger Penrose of Oxford University has pondered this question carefully, examining in turn each of the known laws of physics to see if any one might have uncomputable nooks and crannies. His conclusion is that most of known physics works along Turing lines. But one realm which might go beyond Turing is the boundary between the strange, quantum world of tiny things and the familiar world of ordinary objects ( “Crossing the quantum frontier”, 91av, 26 April 1997, p 38).

One reason that this is a likely candidate is simply that it has been-until quite recently-a theoretical no-man’s land, and the theory proper to this domain remains largely unknown. But whether new and uncomputable physics is at work at this interface, as Penrose believes, remains to be seen.

Aside from any such possibilities, it is now clear that Turing’s conception of computation was rather too strict. And computer science isn’t merely a branch of mathematics after all. The game of searching for machines that can do the impossible has now moved over into the court of the physicists.

* * *

There are some tasks that are simply “uncomputable” for a Turing machine. For example, suppose someone handed you a set of tiles of various shapes and sizes, and asked you whether you could use them to tile an infinitely large floor without leaving any gaps (see diagram).

If they gave you, say, a single tile in the shape of a square, then the answer would obviously be “yes”. But what if they gave you a more complicated set? You might try to use a supercomputer to tell you the answer.

But in 1966, Robert Berger, an American mathematician, proved that there is no way to program a supercomputer-or any other Turing machine-to do this calculation. It might give you an answer. But it might just run on forever without coming to a conclusion, even though there most definitely is an answer. So this problem cannot, in principle, be settled by computation, at least not in Turing’s sense of the word.