Evolving Local Rules to Perform Global Computations

26 Jan 2011 11:36

Some computational problems are very natural and easy in a centralized framework. Say you have a string of bits, and want to count how many of them are 0s. This is trivial, if you have a centralized memory. But suppose you don't; suppose instead you can only perform and record spatially localized operations, where you look at a bit and a few others near it, but do this for each part of the string in parallel. Then it turns out to be very hard to find rules which do well. This is interesting for a number of reasons. One, we're going to be building more and more distributed computers, and so we'd like to understand their scope and limits, and know what we can and cannot ask for in the way of global properties. Two, some of us are just generally into knowing about how local interactions produce global phenomena. Three, lots of biological computation, in particular what brains do, looks an awful lot like decentralized processors with local interactions solving (or faking) global problems, so maybe this will teach us something about ourselves.

Inspired, in part, by the last point, and by the general hardness of the task, quite a few people have turned to genetic algorithms as a way of finding local rules --- especially cellular automata --- which peform globally-simple computations in a decentralized way. Two of the leading test cases are density classification (does the input string contain more 0s than 1s?) and synchronization (get every cell to switch between 0 and 1 together). The point isn't that these are interesting or important tasks in themselves, which has escaped some people. If anything, the point is that these are trivial tasks, which decentralized systems nonetheless find very hard...

See also: Collective Cognition; Duality between Knowledge Centralization and Market Completeness; Evolutionary Design