What does it mean to say that one thing is more complex than another? Like most words,

"complexity" has many meanings. In Chapter 1 we briefly discussed the "complexity" of

computation — of problems and algorithms. In this chapter we will consider several approaches

to quantifying the complexity of individual entities, beginning with the simple Kolmogorov-

Chaitin-Solomonoff definition.

Throughout this chapter, when I speak of computers I will mean ordinary Turing machines,

not stochastic or quantum computers. As yet, no one really knows how to deal with the

complexity of objects in the context of stochastic or quantum computation, not in complete

generality. Since a quantum computer can compute only those functions that a Turing machine

can also compute, this limitation is not fatal.

It turns out that the easiest way to approach the complexity of objects is via the complexity of

sequences of numbers. In particular, I will concentrate on binary sequences: sequences of zeros

and ones. As is common in mathematics, the general issue can be resolved by considering what

at first sight appears to be a very special case.

The standard approach to the complexity of binary sequences was invented independently by

A.N. Kolmogorov, Gregory Chaitin, and Solomonoff (Chaitin, 1987), so we shall call it the KCS

complexity. In my opinion, what the KCS definition measures is not very well described by the

word "complexity." Lack of structure would be a better term.

Given any computer A, the KCS complexity of a sequence x is defined to be the length of the

shortest self-delimiting program on A which computes x. The restriction to "self-delimiting"

programs is necessary for technical purposes and will not worry us much here; roughly speaking,

a self-delimiting program is one which contains a segment telling the computer which runs it

how long it is. In the following, I may occasionally refer to "shortest programs" instead of

"shortest self-delimiting programs"; but it should be implicitly understood thatall programs

discussed are self-delimiting.

For instance, the KCS complexity of the sequence 10011010010010010 on an IBM PC is the

length of the shortest program which, when loaded into the PC, causes it to output

10011010010010010 on the screen. In what follows, I will occasionally refer to the KCS

complexity of a sequence x as KCS(x).

There is some vagueness here, as to what "length" means. For one thing, there are large

differences between the various programming languages on the market today. There are a

number of "high-level" languages, which allow one to type in programs vaguely resembling

mathematical formulae: Fortran, Pascal, Cobol, Snobol, Ada, Prolog, C, Basic, Lisp, Forth, and

so on. A program which is short in Pascal may be long in Cobol; and a program which is short in

Basic may be long in Pascal. And then there is "assembly language", which refers directly to the

hardware of the computer. A program in assembly language is usually very long. However,

before a computer can use a program written in a high-level language, it must translate it into

assembly language. (The program which does the translation is called the "compiler"). When

figuring the length of a program written in Fortran, should we use the number of characters in the

program as originally typed in, or the number of characters in the assembly-language translation

of the program?

From the point of view of the mathematical theory of complexity, none of these issues matter.

We can simply assume we are dealing with a universal Turing machine. Translating from a

foreign language is essentially the same as simulating another computer. So if a sequence is long enough, its KCS complexity is essentially language-independent and computer-independent. For example, say you have a sequence x consisting of a billion 0s and 1s. Suppose it can be

computed by a program of length 1,000,000 on an IBM PC. Suppose a VAX computer has been

programmed to simulate a PC, and suppose this simulation program has length 200,000. Then

the shortest program for computing x on the VAX cannot be any longer than 1,200,000. Because,

if all else fails, one can compute x on the VAX by simulating a PC. These numbers are highly

unrealistic, but the point is that as the sequences get longer and longer, the size of the simulation program remains the same. When the sequences are a trillion digits long, the 200,000 length of the simulation program will mean next to nothing.

Some of the newer programming languages are actually "universal programming languages"

in a very practical sense: any contemporary programming language can be compactly written in

them. For instance, one could write a C program which simulated Pascal or Lisp or Fortran, or a

Lisp program that simulated Pascal or Fortran or C. (In fact, what is now known as Lisp was

originally written in a simpler form of Lisp, and what is now known as C was originally written

in a simpler form of C.) Let’s say a certain sequence x could be computed by a very short Fortran program. Then one way to compute the sequence on a machine with a built-in Lisp compiler

would be to write a Lisp program to simulate Fortran. If there were no simpler way to compute

the sequence in Lisp, this might yield the shortest program forcomputing the sequence on that

particular machine.

Again: the beauty of theoretical computer science is that, as long as we are talking about long sequences, we don’t have to worry about the properties of specific machines or languages. This is what differentiates theoretical computer science from practical computer science. Naturally, the latter is more visible in the everyday world. However, both the theory and the practice of

computer science are essential to the study of mind.

What is the KCS complexity of the sequence 0101010101010101

010101010101010101010101? It should be very small on any computer, because one can write a

program saying "Print ’01’ twenty times". And what is the complexity of the sequence consisting

of 01 repeated 1,000,000,000,000 times? This should still be very small on any computer,

because one can write a program saying "Print ’01’ 1,000,000,000,000 times."

Note that this program is not quite as short as "Print 01 20 times". Our program for repeating

’01’ 1,000,000,000,000 times is 31 characters long, but our program for repeating ’01’ 20 times is only 16 characters long. The difference is, obviously, that it takes more space to write

‘1,000,000,000,000’ than it does to write ’20’. As n increases, the KCS complexity of repeating

something over and over again n times increases. But it does not increase very fast. After all,

1,000,000,000,000 is 50,000,000,000 times as large as 20. But, according to the programs written

above, the KCS complexity of repeating ’01’ 1,000,000,000,000 times is only 31/16 times the

KCS complexity of repeating ’01’ 20 times.

The ratio of program sizes, here 31/16, may vary from computer to computer, from

programming language to programming language. It would be different if this book were written

in Spanish rather than English, because the equivalent of the word "print" would not have exactly five letters in it. But it is difficult to imagine a computer on which it would approach

50,000,000,000. Mathematically, we may say that as n gets bigger and bigger, the size of the

shortest program for repeating something n times gets closer and closer to log(n). This is little more than common sense, because the number of digits in the decimal expansion of a large

number n is always very close to log(n).

What about the KCS complexity of the sequence 010011000111

00001111000001111100000011111100000001111111? This depends on

whether it is shorter to say Print 0100110001110000111100000111110000001111110000000 1111111

or to say

Do the following for k=1, then k=2, and so on up to k=7:

Print k ‘0’s and then k ‘1’s"

In this case the former is a bit shorter. But consider the sequence

01001100011100001111000001111100000011111100000001111111

00000000111111110000000001111111110000000000111111111100000000000

1111111111100000000000011111111111100000000000001111111111111

0000000000000011111111111111? Here there is no doubt that the latter sort of program is

shorter.

Actually determining the KCS complexity of a sequence is a difficult matter. There are

sequences which look completely random and can nonetheless be computed by short programs.

For instance, if one printed the first ten thousand digits of the binary expansion of pi, virtually no human being would recognize any structure in it.

On the other hand, what is the complexity of a sequence x which is completely random in the

sense of having no structure whatsoever? In this case the best way to compute x is to write a

program saying "Print x". This program is about as long as x is. If x has n digits, this program

has length n+c, for some small constant c. In the case of the program as written above, c=5.

According to the KCS definition, a completely structureless sequence such as

10010100101001000011101001101001010010110001100101010001110110101

010001001010010100100101001010110101 is the most complex kind of sequence, with a complexity approximately equal to n. On the other hand, a sequence with a very simple structure, such as 1111111111111111111111, is the least complex kind of sequence, with a complexity approximately equal to log(n). Sequences with more intricate structures fall somewhere inbetween.

It can be shown that no program can compute the KCS complexity of an arbitrary sequence.

For any program P, there is some X the KCS complexity of which P cannot compute.

belgesi-936