Greg Egan 1996. Wang’s Carpets. Kindle Edition. Also as a part of the short story collection by Greg Bear 1996. New Legends. New York: Tor Books. 384 pp; and in several other anthologies.

A mouthfull of a story which later became part of Greg Egan’s novel Diaspora, where many of the threads left hanging are explored more fully.

Humans are now rendered in software, having been scanned generations ago, are now immortal (barring suicide), cloning and reprogramming themselves in large numbers and sending the clones out to explore the galaxy. These missions are seeking evidence of life to confirm their hypotheses of what the meaning of the universe might be. One such voyaging ship has found the first example on planet Orpheus, large “carpets” submerged and slowly moving through an ocean. The carpets hardly seem candidates for sentient life, each one being comprised of a single long carbohydrate molecule. But it turns out they are behaving as a Turing Machine made up of Wang tiles (renamed Wang’s Carpets by the human clones who discovered them).

Wang tiles are a mathematical system proposed by Hao Wang in the form of a conjecture that [simplified version:] square tiles with differently coloured sides can fill an plane, and if so in a periodic pattern. Hao Wang argued that if the such a tiling exists that would imply that there is also an algorithm that would decide if such a pattern exists. Wang’s student showed that there is no such algorithm and the tiling problem is undecidable.

The Wang Carpets on Orpheus are doing that computation, but instead of the simple two-dimensional case proposed by Hao Wang, in this story the carpets occupy many levels in the ocean and thus an immensely powerful computation is going on (and can be visualised by Fourier analysis). An intelligence comprised of a multidimensional Turing Machine.

Searching for more information on Wang Tiles led to a couple of discoveries: An interesting site listing and discussing Mathematical Fiction by mathematician Alex Kasman, which in turn led to:

Physicist, author and musician Catherine Asaro who has published an essay on Wang’s Carpets titled Strange Loops of Wonder and originally published, of all places, in Tangent, a fashion magazine. (Subsequently reprinted in Projections: Science Fiction in Literature & Film edited by Lou Anders; yet another publication to get hold of). Catherine Asaro seems to be one impressive dude and some of her books are now added to my in-tray; also her author page and blog contain many things to read.