I was recently involved in a discussion on **complexity**. Complexity seems like a natural idea – “abababababababababababababababababababababababababababababab” is a simple sequence of letters, while “Whether ‘tis nobler in the mind to suffer the slings and arrows of outrageous fortune” is a complex one. Actually formalising this idea is a little tricky, however. As with some other concepts (*time*, for example), we recognise complexity when we see it, but actually **defining** complexity is difficult. One of the leading approaches is Kolmogorov complexity.

Roughly, Kolmogorov complexity measures the complexity of a sequence by the simplest program that can generate that sequence, which is a formal way of finding the **simplest description** of the sequence. For example, that first sequence is simple because it can be described as “ab”×30.

The simplest programming language I know is combinatory logic (much simpler even than Turing machines). Combinatory logic has all the theoretical power of any other language, but programs are composed only of brackets and the constants `S`

and `K`

(which I will treat as equivalent to 0 and 1). The brackets satisfy `(x y) z = x y z`

. Execution proceeds by term rewriting, and there are just two execution rules:

•`S x y z → x z (y z)`

•`K x y → x`

We can set up a version of Kolmogorov complexity based on combinatory logic. Through Gödel numbering, each program in combinatory logic is associated with a natural number. Execution of the programs gives finite or infinite sequences of `S`

, `K`

, and brackets. I will treat `S`

as 0 and `K`

as 1, ignoring the brackets. I will treat finite sequences as repeating.

Program #0 in the Gödel numbering is just the constant `S`

, which terminates immediately and is equivalent to producing the sequence “0,0,0,…” Program #1 is just the constant `K`

, equivalent to “1…” A slightly more complex program is #96, which is `S S K K S`

, and executes as follows:

1.`S S K K S → S K (K K) S`

2.`S K (K K) S → K S ((K K) S) = K S (K K S)`

3.`K S (K K S) → S`

Execution stops with `S`

in this case, which is equivalent to producing the sequence “0…”

I will take the **simplest** program producing a sequence to be the first program in the Gödel numbering, with the complexity of the sequence being the number of bits in the Gödel number. The two sequences “0…” and “1…” therefore both have complexities of one bit. Repeating pairs have complexities of 2 or 3 bits, while repeating triples have complexity 4 to 6 (see below). Because programs may produce unproductive infinite loops, actual calculation of the complexity of a sequence is not always possible.

Sequence | Program | Complexity |
---|---|---|

010101010101010101010101010101 = 01… | #3 | 2 |

101010101010101010101010101010 = 10… | #4 | 3 |

010010010010010010010010010010 = 010… | #8 | 4 |

001001001001001001001001001001 = 001… | #9 | 4 |

100100100100100100100100100100 = 100… | #13 | 4 |

011011011011011011011011011011 = 011… | #15 | 4 |

101101101101101101101101101101 = 101… | #25 | 5 |

110110110110110110110110110110 = 110… | #49 | 6 |

Some more complex sequences (having non-trivial descriptions) are listed below. The highest complexity will be associated with **random** sequences – which implies that random-number generators are machines for creating complexity. In the images at the top of the page, the random pattern of mineral flecks in granite therefore form the most complex pattern. That may or may not be what we intended the word “complexity” to mean.

Sequence | Program | Complexity |
---|---|---|

010000100001000010000100001000 = 01000… | #141 | 8 |

001010010100101001010010100101 = 00101… | #153 | 8 |

010110101101011010110101101011 = 01011… | #167 | 8 |

000110010001100100011001000110 = 00011001… | #183 | 8 |

010000100010000100010000100010 = 010000100… | #189 | 8 |

001000001000001000001000001000 = 001000… | #198 | 8 |

000101001000101001000101001000 = 000101001… | #201 | 8 |

001000010010000100100001001000 = 00100001… | #216 | 8 |

001000100100010010001001000100 = 0010001… | #233 | 8 |

010100101010010101001010100101 = 0101001… | #251 | 8 |

010101101010101101010101101010 = 010101101… | #275 | 9 |

001100011000110001100011000110 = 00110… | #305 | 9 |

000010000001000000100000010000 = 0000100… | #333 | 9 |

001110110011101100111011001110 = 00111011… | #359 | 9 |

010110010110010110010110010110 = 010110… | #369 | 9 |

001010001010001010001010001010 = 001010… | #392 | 9 |

010100011010001010100011010001 = 010100011010001… | #407 | 9 |

000001010000100000101000010000 = 0000010100001… | #425 | 9 |

001000010001000010001000010001 = 001000010… | #434 | 9 |

010001001000100100010010001001 = 0100010… | #465 | 9 |

001001101001001001101001001001 = 001001101001… | #471 | 9 |