Is there a unique way to determine which rule provides the sequence that matches a finite number of initial steps, choosing the rule that needs the least amount of information to be described?
Example: Three initial steps could be: 1,2,3
A possible rule could be: The sequence described by haviing the first entries be the zeros of the polynomial (x-1)(x-2)(x-3) and zero afterwards, so the sequence would be 1,2,3,0,0,0,...
Another possible rule could be: The sequence of natural numbers, so the sequence would be 1,2,3,4,5,6,...
Is it possible to say that the second rule is better, formalizing this notion with information theory or by any other means?
What you are looking for is Kolmogorov complexity, which is tightly linked with information theory. The sequence $1,2,3$ is a prefix, and every trivial sequence that follows (e.g., all zeros, all ones, increments, periodic repetitions of the prefix, etc.) do not add to the Kolmogorov complexity (except maybe for a "language dependent" constant). Hence, I do not think that there is a unique best choice for the sequence, but actually many.