Kolmogorov complexity vs. intuitive notion of simplicity

Question

Consider the infinite sequence $1,2,4,8,16,...$ If one were asked how the sequence continues the answer would likely be $32,64,..,2^k,..$ and one would implicitly assume the question to be about the "simplest" solution. Mathematically speaking the question is ill posed as there is no universal definition of "simple".

Suppose we are given a finite, increasing sequence $(a_i)$. We define the simplest "infinite expansion" of $(a_i)$ to be the infinite language $L\subseteq\mathbb{N}$ for which we have the shortest Turing machine that recognizes $L$, and (assuming the natural ordering on $L$) $(a_i)$ would be the starting fragment of $L$.

I would like to understand how well this definition agrees with the intuitive (vague) notion of simplicity. Has this been studied before and are there any examples of simplest solutions for some given starting fragment?

Answer 1

For Kolmogorov complexity to make sense one needs a Turing-complete language. Javascript is nice and compact but inconvenient because it doesn't have arbitrary precision, so let's use Python instead. Define a sequence to be a function on the natural numbers starting from $0$. We say that a sequence $f$ is represented in Python3 by a program $P$ iff $P$ halts and the final value of the variable f is a procedure that represents $f$.

Here are some Python3 expressions in order of increasing length (counting new-line as 1 symbol):

Program A0 (length 12; represents $(1,\cdots$)

f=lambda n:1

Program A1 (length 14; represents $(1,2,\cdots$)

f=lambda n:n+1

Program A2 (length 15; represents $(1,2,4,\cdots$)

f=lambda n:1<<n

Program A3 (length 22; represents $(1,2,4,\cdots$)

def f(n):
 return 1<<n

You can see that, for the sequence of powers of $2$, with just the first $1$ or $2$ elements Python3 complexity would favour the wrong sequence (Programs A0,A1). But with just $3$ elements it will favour the right sequence (Program A2). This is because Python3 was designed to be convenient for programmers, so of course you would expect it to favour powers of $2$...

For a more interesting example, consider the following Python3 expressions for initial segments of prime numbers:

Program B0 (length 12; represents $(2,\cdots$)

f=lambda n:2

Program B1 (length 14; represents $(2,3,\cdots$)

f=lambda n:n+2

Program B2 (length 19; represents $(2,3,5,\cdots$)

f=lambda n:n+2+n//2

Program B3 (length 22; represents $(2,3,5,7,\cdots$)

f=lambda n:(n<1)+1+2*n

Program B3 (length 28; represents $(2,3,5,7,11,\cdots$)

f=lambda n:[2,3,5,7,11][n%5]

Program B4 (length 29; represents $(2,3,5,7,11,13,\cdots$)

f=lambda n:(n<1)+1+2*(n+n//4)

Program B5 (length 34; represents $(2,3,5,7,11,13,17,19,23,\cdots$)

f=lambda n:(n<1)+1+2*(n+n//4+n//6)

Program B6 (length 41; represents $(2,3,5,7,11,13,17,19,23,29,31,\cdots$)

f=lambda n:(n<1)+1+2*(n+n//4+n//6+n//9*2)

Program B7 (length 49; represents $(2,3,5,7,11,13,17,19,23,29,31,37,\cdots$)

f=lambda n:(n<1)+1+2*(n+n//4+n//6+n//9*2+n//11*2)

Program B8 (length 55; represents $(2,3,5,7,11,13,17,19,23,29,31,37,41,43,\cdots$)

f=lambda n:(n<1)+1+2*(n+n//4+n//6+n//9*2+n//11*2-n//12)

Program B9 (length 59; represents primes up to $47$)

f=lambda n:[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47][n%15]

(I think such repetition is optimal for all initial segments in-between.)

Program B10 (length 101; represents primes up to $107$)

f=lambda n:[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107][n%28]

Program B11 (length 104; represents primes)

def f(n):
 p=2
 while n>0:
  n,d=n-1,2
  while d>1:
   p,d=p+1,p-1
   while d>1 and p%d>0:d-=1
 return p

If anyone can shorten any of these, let me know in the comments! But if what I have above is optimal, then one needs the first $29$ elements of the sequence of primes for Python3 complexity to favour the correct sequence! Even if what I have is not optimal, I am sure that one needs at least the first $15$ elements. That is much longer than one might expect!