3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ "So there's no such thing as an uncomputable (finite) sequence" there most certainly is, such as the first $n$ busy beaver numbers for large enough but finite $n$. See for example scottaaronson.com/blog/?p=2725. $\endgroup$
    – orlp
    Jun 25, 2018 at 13:20
  • $\begingroup$ @orlp Thanks, good catch. My edit above tries to address it. Is there still any problem re your comment? $\endgroup$ Jun 25, 2018 at 15:39
  • 1
    $\begingroup$ @orlp Certainly any finite sequence of busy beaver numbers is computable (meaning can be output by a TM). And the halting statuses of the TMs in the linked article are also computable. (In fact for each, I can give you a TM right now that computes it.) $\endgroup$ Jun 25, 2018 at 18:42

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
9
  • 2
    $\begingroup$ As an example of what DW is mentioning, consider a series of coin flips. Traditionally, this is considered to be a random process. In fact, I'd argue it's the de-facto standard. Even so, it is entirely possible that a string of $k$ tosses will all land on heads. That is, HHHH...HH is a valid output of this random process, despite the fact that that's probably the easiest polynomial to fit ever! Indeed, if you designed the process to never output "easy fits" like HHH.HHH, you would find that your process has less entropy per character! $\endgroup$
    – Cort Ammon
    Jun 25, 2018 at 15:44
  • $\begingroup$ Thanks. But I was talking about functions, $f_n(i),i=1...n$ that denote the first $n$ integers output by our black-box process. And in the function-as-graph sense, that's just a sequence of numbers. In the function-as-process sense, then as long as $n$'s finite, we can always kludge a polynomial-calculating process to reproduce the graph. But how would you you determine whether or not the $lim_{n\to\infty}f_n$ function is computable? But I guess you got me with random$\not\equiv$computable:) $\endgroup$ Jun 25, 2018 at 15:49
  • 1
    $\begingroup$ @JohnForkosh, it's not clear what the definition of $\lim_{n\to \infty} f_n$ you have in mind (convergence in what sense?), but with the natural definitions I can see, that sequence does not converge and so the limit does not exist (with probability 1 over the random choice of the $f_n$'s), so the question is not well-posed. $\endgroup$
    – D.W.
    Jun 25, 2018 at 15:57
  • 2
    $\begingroup$ @JohnForkosh I think you may be getting at Kolmogorov complexity which is (roughly speaking) a way of describing how hard it is to describe the data seen so far. However, for a random process (such as the coin flipping robot), the Kolmogorov complexity of the first n numbers provides no information about what the n+1 number will be. $\endgroup$
    – Cort Ammon
    Jun 25, 2018 at 16:03
  • 1
    $\begingroup$ @JohnForkosh, see edited answer. $\endgroup$
    – D.W.
    Jun 25, 2018 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.