How could you characterize “true randomness” of a finite sequence?

Question

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 that $1\le f_n(i)\le k$ is the $i^{th}$ number of the experimentally-generated $n$-length sequence. Then we'd want to prove that, given a finite number of such computable $f_n$'s, the function $\lim_{n\to\infty}f_n$ is uncomputable. Can that be done (or provably not done), and would it characterize "true randomness"?

  Edit
---------
Re @orlp's comment, below: Yeah, I guess I phrased that imprecisely. Indeed, you can even construct a more trivial counterexample to my imprecise wording, using the halting problem.

Suppose you claim the have a (let's say C language) function int halts(int n) whose input is the Godel number of a program, and whose output is $1$ if program n halts, or $0$ if not (and let's say $-1$ if n is the Godel number of a string that's not a valid program, just so halts() is a total function on domain $\mathbb N$). Then $\mathbf{\mbox{halts()}:}\mathbb N\to\{0,1;-1\}$.

And let's say ancillary function int godel(char *filename) reads the contents of text file filename, returning its godel number. Now write the following little C program and put it in file doIhalt.c

int main ( int argc, char *argv[] ) {
  int halts(), godel();
  while ( halts(godel("doIhalt.c")) == 1 ) ;
  exit ( 0 ); }

So our doIhalt program runs forever if halts() says it halts, and contrariwise halts immediately if halts() says it runs forever. Thus, if n=godel("doIhalt.c") is the Godel number of that program, the one single number halts(n) is immediately uncomputable. You don't even need a finite sequence at all, as in @orlp's example, to achieve an uncomputable number.

By computability here, however, we're talking about recursive enumerability, whereby the individual elements of our set of integers are given, and the question is whether or not there's a program that enumerates them all. For computer-generated pseudo-random numbers, the answer's a foregone conclusion, "yes". But we're asking about some black-box physical process that's somehow generating number-after-number. And after some finite time we've accumulated a finte sequence of its output. So we obviously have in our hands all those numbers -- that's the premise to begin with. And I was saying, or trying to say, that a finite set of numbers which we "have in our hands" is necessarily computable (meaning r.e.). So how would you say that precisely -- and much more succinctly than I elaborated it above?

In any case, my question then was whether or not the behavior of that black-box physical process is "truly random" -- how could we answer that question given only a finite sequence of the box's output (a prefix string, so to speak).

  Edit#2
-------------
Re @D.W.'s comment below his answer. Okay, considering that the preceding $\lim_{n\to\infty}f_n$ limit isn't well-defined, the alternative standard characterization involves algorithmic complexity, as follows.

First, to briefly recapitulate, we've got a black-box physical process, generating (maybe random) integers, $r_i$, one after another, in the range $1\le r_i\le k$. And for the first $n$ of them, $r_1,r_2,...,r_n$ we construct a function $f_n(i)=r_i,\ i=1...n$. So $f_{n+1}$ might necessarily be very different than $f_n$, or it might be quite similar.

Note that a program for the simplest $f_1$ function would just store $r_1$ and print it. Any kind of algorithm to compute that one-number-domain function would surely be more complicated than just printing it. Indeed, let $K(f_n)$ denote the Kolmogorov/algorithmic complexity of (the simplest program that computes) function $f_n$. So the first few $f_n$'s probably just store-and-print all the corresponding $r_i,\ i=1...n$.

But eventually, as $n$ gets large enough, storing-and-printing would presumably not be the shortest/simplest way to generate all the necessary $n$ values $r_i,\ i=1...n$. The length/complexity of an algorithm would be shorter than all the necessary data. But, of course, that's >>only if<< there exists such an algorithm in the first place.

So, for a pseudo-random number generator, we know there's an algorithm. So $lim_{n\to\infty}K(f_n)=const$ because that same algorithm computes as many random numbers as you like. Otherwise, for "truly random" sequences, the limit diverges because there's no algorithm, and there's ultimately no alternative to storing-and-printing all the data.

I'm not sure whether or not the above satisfies all (or even some of) @D.W.'s objections below, but in any case, given a finite "prefix string" of the black-box's output $r_i,\ i=1...n$, you still can't tell (I don't think) whether or not that $K(\cdot)$ limit converges.