An introduction to algorithmic information theory PART 1

I will be posting a series of posts that is an introduction to algorithmic information theory (AIT), that will be needed for my coming posts.

Don't miss my previous post (which actually already used some AIT, so you should read the post you are reading now first):
Why mathematics is NOT unreasonably effective in describing nature

Algorithmic information theory deals with the complexity of individual pieces of information, often represented as a finite string of bits (ones or zeroes). For example:

x = 01001000101110101101001010101111001010100

´

Alan Turing

First one defines a Turing machine (TM) by abstracting the most general way a mechanical, determinitic, finite set of rules can be represented.

For an informal definition, a Turing machine, T, is simply a calculating apparatus, that for any finite input (a string of bits) either halts after a finite number of steps and outputs a finite string of bits, or never stops. However a Turing machine is allowed to have infinite working memory.

A universal Turing machine (UTM), U, is a Turing machine that can simulate any other Turing machine, and there exist such machines. Practically all computers used in everyday use are UTM's, except for the part about the infinite working memory.

If U is a UVM, then for any Turing machine, T, and any input to T, x, U can simulate T accordingly:

U(<n_T, x>) = T(x)

´

Here n_T is the Turing machine T encoded as a string of bits. This can always be done since there is countably many TM's, so we can count them, T0, T1, T2... Also, <x,y> denotes a bitstring that contains x and y and a way to tell them apart. Also, the length of a bitstring, x, is denoted by: l(x). So for example l(01011)=5.

Now we can define the algorithmic complexity, or the Kolmogorov complexity, of a bitstring, x as the length of a shortest bitstring, here called a program, p, fed into a UVM, U, that gives x as its output and then halts. The bit about the "and then halts" is absolutely necessary!

K(x) = min {l(p) : U(p)=x}

´

To see that K(x) is always finite, note that one can for any x always create a trivial program that explicitly mentions x within it, for example:

print("101001001001001001");
halt;

´

This program prints out the string 101001001001001001 and then halts. The length of the program is about the same as the length of 101001001001001001, plus some extra space required to encode "print" and "halt" in binary. The interesting thing is when there are programs much smaller than a string, x, that prints out x and halts. For example the string "01" repeated 10^100 times is very large, but this program in pseudocode does the job:

for (i in 1:10^100){
    print("01");
}
halt;

´

The size of this program in bits must be much smaller than 10^100, but can still print the huge string "01" repeated 10^100 times. This string therefore has low Kolmogorov complexity.

How do we know if there are strings with Kolmogorov complexity roughly equal to their own size? Such a string would be "incompressible" or "patternless" in an algorithmic sense. That will be explored in my next post.

Lastly, let us define a one-to-one correspondence between natural numbers and finite bitstrings accordingly:

Λ = 0 (the empty string)
0 = 1
1 = 2
00 = 3
01 = 4
10 = 5
11 = 6
000 = 7
001 = 8
and so on...

´

I will assume this correspondence in the remainder of the upcoming articles, bitstrings are just natural numbers and vice versa.

Here is my next post:
An introduction to algorithmic information theory PART 2