Was discussing pseudo-random number generators with a colleague, around desirable attributes of the distribution, periodicity, etc — all fun and important stuff.
It reminded me of a chain of thought ranging from complexity theory to the philosophical. Pardon the armchair physics and philosophy.
As we know from information theory, any sequence generated by an algorithm with no exogenous input, except perhaps an initial state, cannot be random. There are multiple measures of randomness in theoretical computer science around measuring the degree of pattern in a given sequence (or string). One that appeals to me, is the Kolmogorov complexity measure (I was reminded of this by recent posts on Shtetl-Optimized) which is approximately:
for some string x (say a random sequence we are testing), what is the shortest possible program in some universal computer language K(x) that prints x and halts.
Intuitively, if a sequence is truly random, there is no algorithm that can generate it short of the sequence literal itself. Assuming we a looking at very long sequences of X (our random sequence), the program to produce that must also be very large (as long as the literal) and hence have a very high K(x) measure. A long pseudo random sequence may look to be quite complex at first glance, but can be described by a short program generating the sequence, and hence has a low K(x) measure.
Not being a complexity theorist, I’m playing pretty loose with the definition, but you get the idea.
Going further, one thing I’ve often thought about, is whether randomness truly exists in the universe. This may be equivalent to asking, is the universe computable. This question and theory around this has been proposed and discussed since the 1950s. Are the random distributions we see in quantum states, for example, just manifestations of a complex computable function, probably one with many dimensions and long periodicity.
If the fabric of the universe is computable, then it stands to reason that what is contained within is also. In this scenario, we being computable machines made of this macro-stuff called matter, are just very complex functions of our initial states; Not just our initial state (our conception and program therein), but the state vector of all influences in the universe, our surroundings, and other automata.
Well you can see where this goes. Free will is a function of our reason and environment, but our reasoning function is also predetermined by this astronomical state vector / ongoing computation.
Anyway, I was reluctant to post this for a while, but thought it would be fun for a change. Starts with science and ends with philosophical possibility.
Addendum
I should add, the data we receive from “random” physical processes appears to be random. If we assume a computable universe, the generating function for these random processes could be vast given the possibility of an “astronomical”, but finite, number of inputs (or dimension). i.e. Our approximation of the K(x) function appears to be large just because we do not know how to determine the generating function. Hence in a short life-time of observation and computation, such a function would have the appearance of randomness (as in maximal complexity) and infinite period.
