How to find the minimal description for an array?

Question

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?

Answer 1

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.

Like all interesting properties of Turing machines, the Kolmogorov complexity of a string is undecidable. However, this doesn't stop it being a useful concept and there's been a large amount of research on the subject.

Answer 2

If you look at this from a practical POV you can call it data compression. This is basically what data compression algorithms do: They define a language, and then try to represent the given data set in this language. But even for a very simple language it is very hard to find the optimal representation in that language. Take for example Deflate, despite being very simple there is still active research in how to apply it in an optimal way.