Looking for aliens in the computational universe

From New Scientist - Permutation City's Lambertians?

IN The shadows of Mount Shasta and Lassen Peak volcanoes in northern California, dozens of radio telescopes are gearing up to search for extraterrestrials. Thousands of kilometres away in Boston, Massachusetts, Stephen Wolfram has the same goal in mind. But unlike the astronomers working at Hat Creek observatory, Wolfram's approach has no need for telescopes.

Instead of scanning the heavens for alien radio broadcasts, he thinks we should be looking much closer to home. Much, much closer: ET could be living or working with you. But the truly amazing thing about Wolfram's claim is that he believes all the knowledge we stand to gain from an extraterrestrial intelligence - surely the best reason for getting to know the alien in the first place - is already ours for the taking. We don't have to find ET; we can start the search for this ultimate knowledge right now. Advanced civilisation could be little more than a mouse click away.

Wolfram is used to making controversial claims. Three years ago he published a hefty book with an equally weighty assertion: that scientists have been thinking about the universe the wrong way. If we really want to understand nature's complexity, he argued, we need to go beyond mathematics with all its complicated equations and symbols. Instead we should be embracing "a new kind of science" - as he titled his book - in which the answers to science's most difficult problems lie in simple computer programs.

But Wolfram, the multimillionaire inventor of Mathematica, the world's most popular mathematics software, hasn't stopped at attempting to redefine the nature of scientific inquiry. His work with A New Kind of Science got him thinking about how similar ideas might affect other human endeavours. One that sprung to mind almost immediately was SETI, the search for extraterrestrial intelligence.

"Everything I've done over the past 20 years has taught me that SETI as currently practised is not the most sensible thing to do," he says. Which is why he has tried to redefine the best way forward for discovering alien intelligence in the universe. A new kind of SETI, if you will.

Alien artefact or star?

The problem with SETI as it stands is that it is groping in the dark with no idea what to grope for. Today's SETI researchers look for the interstellar equivalent of a radio station. Terrestrial radio broadcasts imprint music and chatter by varying the amplitude or frequency of an electromagnetic wave oscillating at a certain frequency. So SETI scientists sift through the chaotic babble of interstellar radio noise for a signal that has some kind of regular pattern.

But there's a problem with this approach: patterned signals are notoriously inefficient. To transmit a "1" followed by a "0" repeated a million times would mean hogging a frequency band until you finished sending the message 101010... Instead you could exploit the regular pattern of 1s and 0s to speed up transmission. In this case your message would simply be "repeat '10' a million times". Such a compressed message would be a far more efficient use of resources. "Because a patterned signal is so inefficient, it is very unlikely to be the kind of thing used by an advanced technology," says Wolfram.

You can already see the trend here on Earth. Our communications have become more sophisticated as we have become more advanced. To make them more efficient, we are cramming as much information as possible into a signal. This has led to technologies that exploit a vast number of frequencies simultaneously, such as CDMA (code division multiple access), a cellphone standard used in North America.

In CDMA, the carrier is a sequence of compressed binary digits rather than a simple sinusoidal wave. "What is being transmitted looks almost random," says Wolfram. He concludes that the transmissions of an advanced civilisation will be as far as you can get from the patterned signals that SETI scientists are looking for. In fact, they will look pretty much like the random radio noise we associate with astrophysical sources such as stars and interstellar gas clouds.

So how can we distinguish between a signal from an extraterrestrial intelligence and natural background noise? "It's going to be extremely hard," Wolfram admits. "The only way to do it is by a process of elimination."

Take radio emission from our galaxy, for example. For each candidate ET signal, we would need to rule out all the natural sources that might contribute, including pulsars, clutches of newborn stars and cold gas clouds. "We can then say that what is left over may be an intelligent signal," says Wolfram.

Of course, that is a big "may be". The leftover radio emission could have a natural cause that we simply do not know about yet. "Even if we were to find a transmission containing the digits of pi, it is always possible that a natural process could be generating it," says Wolfram. As a result, we will never be sure that a signal we have picked up is from an extraterrestrial intelligence, Wolfram reckons. "The question 'is this an intelligent signal?' is very unlikely to have a simple yes/no answer," he says.

“We don't have to speak to advanced beings to learn their secrets. We can hunt for nuggets of useful information for ourselves”
Of course, extraterrestrials could be so clever that they realise they need to talk down to us. "They may use a deliberately beamed beacon that, by design, will be energy inefficient, directional and easily detected by our present methods," says Paul Shuch of the SETI League in Little Ferry, New Jersey.

But it is highly unlikely that ET would adapt a signal just for us. "It would mean tailoring a signal for a civilisation that has developed radio communication but has not yet developed efficient radio communication," Wolfram points out. "That's an awfully brief window in time."

He is equally pessimistic about our chances of spotting an artefact deliberately left by ET for us to find. In March, Luc Arnold of the Haute-Provence Observatory in St Michel, France, suggested that one possible way to search for extraterrestrial intelligence is to look for artificial structures, such as giant triangles orbiting stars (The Astrophysical Journal, vol 627, p 534). These objects might simply be alien artefacts or a way for ET to communicate across vast tracts of the Milky Way.

Arnold's idea is based on the fact that astronomers can already detect planets orbiting nearby stars if they happen to pass in front of their parent star, temporarily dimming its brightness. His work shows that you could distinguish the dimming caused by a strangely shaped object from that resulting from a passing planet, in much the same way that it is easy to spot the difference between objects we have built and natural phenomena - buses and trees, for example. That's because nature's artefacts are always more complex than our own. But Wolfram believes this will change in the future as we become more intelligent. "All artefacts will be as complicated, if not more, than nature's."
Computational universe

And that is bad news for SETI. The complex artefacts made by an advanced civilisation would be worlds apart from the simple, giant triangles Arnold envisages. In fact, they could look very much like natural objects. Which poses a remarkable question: are the stars extraterrestrial artefacts? "They could have been built for a purpose," says Wolfram. "It's extremely difficult to rule it out."

It seems that searching the physical universe for signposts, message-laden radio waves or light beams is going to be far harder than anyone imagined. But there's no need for despair. Who says we're stuck with just searching the physical universe?

At the heart of Wolfram's new kind of SETI is the idea of a "computational universe", a vast collection of all the possible computer algorithms that can ever exist. Within the computational universe lies every answer - and every being - that we could want to find.

The concept is based on Wolfram's previous work, which shows how simple rules can generate the complexity we see around us, from turbulent fluids to galaxies. Even life itself is the product of a simple algorithm that takes amino acids as its input and churns out proteins that interact with each other in myriad ways. The rules that generate turbulence, galaxies and life are just a handful of examples from the computational universe.

It might sound odd to think that these algorithms simply exist, rather than being written by us. But Gregory Chaitin, a mathematician based at IBM's T. J. Watson Research Center in Yorktown Heights, New York, has long claimed that mathematical theorems are discovered rather than created (New Scientist, 10 March 2001, p 28).

Similarly, theoretical computer scientists think of programs rather as we think of sentences: an almost infinite cauldron of possibilities. If you wrote down every possible sentence in the English language and grouped as many of them as you liked in different ways, you would have an infinite list. Most of the permutations would be gobbledegook. But buried amongst them, you would find War and Peace and Hamlet. So when we find algorithms that encrypt data or add up the numbers on a spreadsheet, we are effectively plucking them from the computational universe.

But how do you make the leap from a spreadsheet to aliens? To Wolfram, humans are an example of a simple algorithm that has a particularly complicated outcome. By the same logic, so are extraterrestrials. That means that they exist in the computational universe too. "We can look for extraterrestrial intelligence in the physical universe or in the computational universe," says Wolfram, "but the task is a lot easier in the computational universe and there's a lot more there."

Wolfram is not trying to be controversial; he's trying to help. He is a SETI enthusiast, he says, and he thinks this new line of attack provides a fast-track to the SETI prize. Computer power is increasing faster than our ability to search stars for alien signals, so Wolfram claims it makes more sense to switch our attention to the abstract computational universe.

And, he says, he has already started. A New Kind of Science marked the start of a systematic trawl through the computational universe. It charts the outcome of computer programs called cellular automata, in which patterns form and evolve on a grid according to a simple rule. To see how they work, imagine a row of white squares with a single black square in the middle. Cellular automata are rules that dictate what colour each square should take in the next row down based on its colour and the colour of its neighbouring squares. By applying the rule again and again, you can produce extremely complicated patterns reminiscent of the complexity we see in the real world (New Scientist, 6 July 2002, p 46).

So far Wolfram has only scratched the surface of the computational universe. A New Kind of Science starts by detailing the outcomes of the 256 simplest rules. But the surprising degree of complexity that arises from such a simple scenario hints that we might not have to look too far to find the instructions that tell us how to assemble ET for ourselves.

The next step is to look for more complex rules and work out their outcomes. That could take a long time - it took Wolfram nearly two decades to study the 256 possible rules that you can formulate using just three black and white squares arranged in a one-dimensional line. Adding another dimension or even adding another colour vastly increases the number of possible rules.

Of course, if we find it, the ET in your PC won't be a flesh-and-blood alien, it will be a cyber version. But that doesn't mean we can't communicate with it; we could still converse with a virtual version of an alien civilisation, and learn plenty from the conversation.

And, Wolfram says, we could also cut out the middleman. We don't have to speak to advanced beings to learn their secrets; there is nothing to stop us hunting for nuggets of useful information for ourselves. After all, as Wolfram points out, if we can find algorithms for aliens, we can find algorithms for what they know. "The truth is, it is more efficient for us to simply search the computational universe ourselves," says Wolfram. "What could extraterrestrials tell us apart from 'we've done more computations than you and here are some good algorithms we've found'?"

Indeed, Wolfram views the search for useful algorithms in the computational universe as the modern equivalent of searching for useful commodities, such as spices. Except, of course, it might take a lot longer. No one knows how long it will take to search the computational universe for useful answers; one of the main criticisms of Wolfram's idea is that the only way to find the eventual outcome of some programs is to run them for billions of years.

And who's to say that we would even recognise ET if we stumbled across an alien-making algorithm. Perhaps the alien in our computer is already trying to get our attention. Could Microsoft Office's paper clip really be trying to tell us something?