快猫短视频

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鈥檚 College, Cambridge, had an idea for an incredible theoretical gadget. Turing believed that his imaginary gadget-known today as a 鈥淭uring machine鈥�-could carry out any process that might conceivably be called a 鈥渃omputation鈥�. In effect, the machine gave mathematical substance to the informal notion of what it means to 鈥渃ompute.鈥� It was an ingenious invention, and only ten years later, following the Second World War, it was with Turing鈥檚 machine firmly in mind that teams of scientists in the US and Britain- including Turing himself-built the first general purpose computing machines.

Turing鈥檚 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鈥檚 machine. And yet recently, scientists have begun to think again about the notion of computation, and to wonder if Turing鈥檚 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鈥檚 common to talk about doing a 鈥渃omputation鈥�. 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 鈥渁lgorithms鈥�.

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鈥檚 model-his 鈥渕achine鈥�-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 鈥渦niversal鈥� Turing machine, can emulate the action of any other Turing machine. This includes any modern digital computer. So Turing鈥檚 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鈥檚 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: 鈥淎 Turing machine running a suitable program can carry out any process that can reasonably be called a computation.鈥�

The Turing-Church 鈥渢hesis鈥� is not a theorem because it鈥檚 not really amenable to proof. It鈥檚 more of a proposal, suggesting that we agree to equate our informal idea of computation with Turing鈥檚 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 鈥渉ard鈥� 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鈥檚 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鈥檛 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 鈥渆asy鈥� 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 鈥渢ile鈥� 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 鈥渆asy鈥�, 鈥渉ard鈥� and 鈥渦ncomputable鈥� holds only within the framework of Turing鈥檚 model. In the past few years, mathematicians and scientists have suddenly woken up to the fact that the Turing-Church thesis isn鈥檛 beyond doubt, and have begun to explore the world of exotic computing machines that fall outside Turing鈥檚 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 鈥渆asy鈥�, 鈥渉ard鈥� and 鈥渦ncomputable鈥� 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 鈥渟treet-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 鈥淒NA computer鈥� makes all possible chains, and so, checks all possible paths at once. It鈥檚 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鈥檚 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 鈥淪imulating 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 鈥渟uperposition鈥� 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鈥檚 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 鈥渂eyond 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. 鈥淲hat computers can and cannot compute is determined by the laws of physics,鈥� says Deutch, 鈥渘ot 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鈥檛 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鈥檚 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 鈥渞eal 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 ( 鈥淐rossing the quantum frontier鈥�, 快猫短视频, 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鈥檚 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鈥檚 conception of computation was rather too strict. And computer science isn鈥檛 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 鈥渦ncomputable鈥� 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 鈥測es鈥�. 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鈥檚 sense of the word.