Saturday 11 May 2013

Universal computation and universal Darwinism

Universal computation describes systems in terms of their relationship to abstract computing devices which are capable of computing anything that can be computed.

Universal Darwinism characterizes systems in terms of how they change over time - and divides their dynamics into copying, selection and variation.

This post will consider how these ideas are related. In particular, it will consider computation in the light of Darwinism.

There are various models of universal computers, but they all have equivalent capabilities. One way of making a universal computer involves interconnect and NAND gates. NAND gates have the property known as functional completeness - which means that they can be connected together to emulate any other logic gate or computational system. The truth table for a NAND gate looks like this:

NAND truth table

Input Output
A B
0 0 1
0 1 1
1 0 1
1 1 0

Branching interconnect results in signals being copied - from the "input" branch to all the "output" branches. The NAND gate itself results in selective data transmission. You can see this by considering that when A is 0, the signal from B is destroyed[1], while when A is 1 the signal from B is transmitted through. It is true that the signal from B is inverted - but that's an information-theory null-op: if you want the original signal back, you can just invert it again.

So: computers exhibit copying and selection ubiquitously - what about variation? Variation arises inside computers too. Variation is just copying that is inaccurate or incomplete - and of course, this happens all the time.

This characterization of computation in Darwinian terms is helpful - since it allows the large body of theory descended from Darwin's work to be applied to computers and computer networks. Indeed, according to the computability thesis, any physical system can be emulated by a universal computer - so the domain of these theories includes all physical systems.

[1] What about reversible computers? Selection doesn't depend on the destruction of information. It is enough for the information to go into a trash basket somewhere. So, the same argument can be applied to Fredkin gates.

No comments:

Post a Comment