5

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?

  • I was just going to write Kolmogorov complexity is probably interesting but you already had it in the tags so I suppose you know about it. Maybe not only shortest length of computer program as a text string in a computer language but also fewest number of elementary operations by the computer could be interesting. I don't remember which of those is what is defined as the Kolmogorov complexity – mathreadler Jul 13 '17 at 09:34
  • If the computer has a machine instruction to compute something which is faster than multiplying by two you maybe could argue it is "simpler". For example a machine working with representations other than binary where multiplication by two is not as easy to make fast compared to other operations. – mathreadler Jul 13 '17 at 09:44
  • Your "definition" leaves out the problem of halting, it's undecidability. "The shortest halting program such that... " isn't always a meaningful phrase. And even if you restrict yourself to some halting grammar, the ordering of programs by size isn't likely to match the human ordering of programs due to the differences of primitives. – DanielV Jul 14 '17 at 14:26
  • @DanielV I'm afraid I don't follow you. What is a halting grammar? –  Jul 16 '17 at 05:20
  • @FFF In some computing models, everything halts. Typed lambda calculus, primitive recursive equations are 2 examples. In some computing models, there are programs that don't halt. General lambda calculus and Turing machines are 2 examples. There is a general diagonalization argument to show that you can't enumerate all halting programs anyway. – DanielV Jul 16 '17 at 17:12
  • @DanielV Yes, I'm familiar with these facts, but how these are related to the question? My definition is a (seemingly?) natural extension of Kolmogorov complexity, which itself is non-computable, thus the question is about a non-computable property anyway. –  Jul 16 '17 at 17:37
  • I didn't mean to throw off your whole question, just since you went to the effort of trying to make a formal definition I didn't want to leave a potential poster with the idea that "the shortest TM implementing P" is a totally defined concept the same way that "the smallest integer with property P" sometimes is. – DanielV Jul 16 '17 at 18:02

1 Answers1

3

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!

user21820
  • 57,693
  • 9
  • 98
  • 256
  • Having such a huge number of primitives misses the point of kolmogorov complexity. The "size" of your programs is underestimated because it doesn't include the definitions of things like "<<". If you are going to have so many primitives, then everything can just be $\lambda n . g n$ where $g$ is a language extension that implements the start of the sequence. – DanielV Jul 14 '17 at 14:30
  • 2
    @DanielV: It's the same with any programming language, whether or not you're using some cumbersome encoding of Turing machines on a 1-tape Turing machine with only 1 non-blank symbol or something like that. The advantage of using a popular programming language is that it can be used as a standard reference. Since Kolmogorov complexity is asymptotically equal up to an additive discrepancy, this works for nearly every sequence. Anyway, I was careful to state "Python3 complexity", and I even chose the sequence of primes as a good example since Python doesn't have it as a primitive. – user21820 Jul 14 '17 at 14:35