Algorithmic Complexity

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

Belgeci