How could you characterize "true randomness" of a finite sequence?

This question occurred to me while reading http://arxiv.org/abs/1806.08762/ Any observed sequence is necessarily finite, and any finite sequence is computable, either by explicitly storing all the data and just printing it, or by fitting an $n^{th}$-degree polynomial to an $n$-length sequence, etc.

So there's no such thing as an uncomputable (finite) sequence, whereby the article's title "Experimentally probing the incomputability of quantum randomness", initially struck me as somewhat of a non-sequitur (although the details of the article made somewhat more sense of it).

But pursuing the classical non-sequitur sense that initially occurred to me, suppose you have some process purported to be "truly random". So prove it!   At best, you can give me a finite sequence generated by that process. Then I just fit a polynomial to it, and poof, it's pseudo-random. So my question... what analysis of such a finite sequence would prove that in the $n\to\infty$ limit, your finite pseudo-random sequence would be truly random (or, in some epsilon-delta sense, approach true randomness to any desired accuracy)?

For definiteness and simplicity, and for another argument, suppose we're talking about a sequence of random integers from, say, $1$ to $k$. Then there are $k^n$ $n$-length sequences, and not only can we fit a polynomial to each one, we can use some standard enumeration to enumerate them all. Then, choosing a single (random or not) number $1\ldots k^n$ corresponds to choosing an entire (random or not) sequence. But "single numbers" aren't typically considered random in the first place, whereby (one might argue) neither should finite sequences be. So, again, how could you prove that the $n\to\infty$ limit of the sequence generated by a physical (and supposedly random) process is truly random?

What occurred to me as a possible answer is that if "truly_random"$\sim$uncomputable, then consider a sequence of computable functions, say our polynomials $f_n(i), i=1\ldots n$, such

Answer to original question:

Your question is based on some faulty premises and misunderstandings.

A word/string is neither computable nor uncomputable. Rather, we apply uncomputability to languages (sets of strings), or to functions. See https://en.wikipedia.org/wiki/Formal_language and https://en.wikipedia.org/wiki/Computable_function.

You can't prove that a source is random by looking at a single output from it (and this has nothing to do with computability or uncomputability). Instead, the way you prove a source is random is by proving something about the process that generates it. See How best to statistically verify random numbers?. So, being able to find a pattern in a single output of some source (e.g., being able to fit a polynomial to that output) neither proves that the source is random nor that the source is not random.

Finally, "truly random" is not equivalent to "computable". They are not really comparable concepts.

Answer to edit #2:

I think you are asking about the Kolmogorov complexity of a random sequence. In particular, let $r_1,r_2,r_3,\dots$ be chosen uniformly and independently at random from $\{1,\dots,k\}$, and let $f_n:\{1,\dots,n\} \to \{1,\dots,k\}$ be the function defined by $f_n(i) = r_i$. Then with probability 1,

$$\lim_{n \to \infty} K(f_n) = \infty,$$

and in particular, with probability exponentially close to 1, we have $K(f_n) = n + O(1)$, so $K(f_n) \to \infty$ as $n \to \infty$. This means that you can't save much space compared to "store-and-print" (with high probability, no more than a constant number of bits).

Of course, the Kolmogorov complexity is not computable, so this is not a useful way to distinguish random data from pseudorandom data.

StackExchange Computer Science Q#93479, answer score: 6