# How to find the minimal description for an array?

The following array occupies 10000 slots in memory:

a = [0,1,2,3,4,5,6,7,8,9,10,...,10000]


But one could easily represent the same array as:

a = {len:10000, get: λ idx -> idx}


Which is much more compact. Similarly, there are several arrays that can be represented compactly:

a = {a:1000, get: λ idx -> idx * 2}
Is a description for [0,2,4,6,8,10,...,2000]

a = {a:1000, get λ idx -> idx ^ 2}
Is a description for [0,1,2,4,9,...1000000]

And so on...


Providing so many arrays can be represented in much shorter ways than storing each element on memory, I ask:

1. Is there a name for this phenomena?
2. Is there a way to find the minimal representation for a specific array?
3. Considering this probably depends on the language of description (in this case, I used an imaginary programming language with functions, objects and math operators). Is there a specific language that is optimal for finding that kind of minimal description for objects?

The phenomenon you're describing is Kolmogorov complexity. Essentially, if you fix a programming language (or, more formally, a coding of Turing machines) then the Kolmogorov complexity $K(s)$ of a string $s$ is the length of the shortest program that outputs $s$ when started with no input. It turns out that, within reason, it doesn't matter what programming language you use, since using a different language makes at most a constant additive difference to $K(s)$. If you want to define Kolmogorov complexity with respect to some whacko language, I can just use that language to write an interpreter for a sensible language, so the Kolmogorov complexity of a string with respect to your language cannot be worse than the complexity in my language plus the fixed, constant overhead of the interpreter.