La complejidad de Kolmogorov frente a la noción intuitiva de simplicidad

Question

Consideremos la secuencia infinita $1,2,4,8,16,...$ Si se preguntara cómo continúa la secuencia, la respuesta sería probablemente $32,64,..,2^k,..$ y uno supondría implícitamente que la pregunta se refiere a la solución "más sencilla". Desde el punto de vista matemático, la pregunta está mal planteada, ya que no existe una definición universal de "simple".

Supongamos que nos dan una secuencia finita y creciente $(a_i)$ . Definimos la "expansión infinita" más sencilla de $(a_i)$ para ser el lenguaje infinito $L\subseteq\mathbb{N}$ para el que tenemos la máquina de Turing más corta que reconoce $L$ y (asumiendo el orden natural en $L$ ) $(a_i)$ sería el fragmento inicial de $L$ .

Me gustaría saber hasta qué punto esta definición coincide con la noción intuitiva (vaga) de simplicidad. ¿Se ha estudiado esto antes y hay ejemplos de soluciones más sencillas para algún fragmento inicial dado?

Answer 1

Para que la complejidad de Kolmogorov tenga sentido se necesita un lenguaje Turing-completo. Javascript es bonito y compacto, pero es un inconveniente porque no tiene precisión arbitraria, así que vamos a utilizar Python en su lugar. Definamos una secuencia como una función sobre los números naturales a partir de $0$ . Decimos que una secuencia $f$ se representa en Python3 mediante un programa $P$ si $P$ se detiene y el valor final de la variable f es un procedimiento que representa $f$ .

Aquí hay algunas expresiones de Python3 en orden de longitud creciente (contando la nueva línea como 1 símbolo):

Programa A0 (longitud 12; representa $(1,\cdots$ )

f=lambda n:1

Programa A1 (longitud 14; representa $(1,2,\cdots$ )

f=lambda n:n+1

Programa A2 (longitud 15; representa $(1,2,4,\cdots$ )

f=lambda n:1<<n

Programa A3 (longitud 22; representa $(1,2,4,\cdots$ )

def f(n):
 return 1<<n

Se puede ver que, para la secuencia de potencias de $2$ con sólo la primera $1$ o $2$ elementos La complejidad de Python3 favorecería la secuencia incorrecta (Programas A0,A1). Pero con sólo $3$ elementos favorecerá la secuencia correcta (Programa A2). Esto se debe a que Python3 fue diseñado para ser conveniente para los programadores, así que por supuesto se espera que favorezca las potencias de $2$ ...

Para un ejemplo más interesante, considere las siguientes expresiones de Python3 para segmentos iniciales de números primos:

Programa B0 (longitud 12; representa $(2,\cdots$ )

f=lambda n:2

Programa B1 (longitud 14; representa $(2,3,\cdots$ )

f=lambda n:n+2

Programa B2 (longitud 19; representa $(2,3,5,\cdots$ )

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

Programa B3 (longitud 22; representa $(2,3,5,7,\cdots$ )

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

Programa B3 (longitud 28; representa $(2,3,5,7,11,\cdots$ )

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

Programa B4 (longitud 29; representa $(2,3,5,7,11,13,\cdots$ )

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

Programa B5 (longitud 34; representa $(2,3,5,7,11,13,17,19,23,\cdots$ )

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

Programa B6 (longitud 41; representa $(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)

Programa B7 (longitud 49; representa $(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)

Programa B8 (longitud 55; representa $(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)

Programa B9 (longitud 59; representa primos hasta $47$ )

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

(Creo que esta repetición es óptima para todos los segmentos iniciales intermedios).

Programa B10 (longitud 101; representa primos hasta $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]

Programa B11 (longitud 104; representa los primos)

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

Si alguien puede acortar alguna de ellas, que me lo diga en los comentarios. Pero si lo que tengo arriba es óptimo, entonces se necesita la primera $29$ ¡elementos de la secuencia de primos para que la complejidad de Python3 favorezca la secuencia correcta! Incluso si lo que tengo no es óptimo, estoy seguro de que se necesita al menos el primer $15$ elementos. Es mucho más largo de lo que cabría esperar.