“But we don’t know how to program robots very well,” Bongard says, because robots are complex systems. In some ways, they are too much like people for people to easily understand them.

“They have lots of moving parts. And their brains, like our brains, have lots of distributed materials: there’s neurons and there’s sensors and motors and they’re all turning on and off in parallel,” Bongard says, “and the emergent behavior from the complex system which is a robot, is some useful task like clearing up a construction site or laying pavement for a new road.” Or at least that’s the goal.

Using a sophisticated computer simulation, Bongard unleashed a series of synthetic beasts that move about in a 3-dimensional space. “It looks like a modern video game,” he says. Each creature -- or, rather, generations of the creatures -- then run a software routine, called a genetic algorithm, that experiments with various motions until it develops a slither, shuffle, or walking gait -- based on its body plan -- that can get it to the light source without tipping over.

“The snake and reptilian robots are, in essence, training wheels,” says Bongard, “they allow evolution to find motion patterns quicker, because those kinds of robots can’t fall over. So evolution only has to solve the movement problem, but not the balance problem, initially. Then gradually over time it’s able to tackle the balance problem after already solving the movement problem.”

('Lego robot built as proof of concept)

Science fiction writers seem quite cautious about the idea of robots that evolve on their own. In his 1953 short story Second Variety, claws that come up from underground seem to demonstrate machine evolution:

The new varieties of claws. We're completely at their mercy, aren't we? By now they've probably gotten into the UN lines, too. It makes me wonder if we're not seeing the beginning of a new species. The new species. Evolution. The race to come after man."

More recently, Rudy Rucker described boppers, self-reproducing robots that changed their shapes at will:

In the shaft's great, vertical tunnel, bright beings darted through the hot light; odd-shaped living machines that glowed with all the colors of the rainbow. These were the boppers; self-reproducing robots who obeyed no man. Some looked humanoid, some looked like spiders, some looked like snakes, some looked like bats. All were covered with flickercladding, a microwired imipolex compound that could absorb and emit light.

If you're interested in robots that are able to deal with changes in their shape, read about the starfish robots created at Cornell university; these robots walk after conceptualizing their own structure.