Is this mathematical answer to randomness question philosophically satisfying?

Question

The question was asked on this page

Is there anything that is totally random?

but I was not allowed to answer due to lack of reputation. Yet I wonder if my mathematical answer that follows is acceptable to philosophers.

I will limit myself to the finite strings of 0s and 1s. We say that such a string is reducible if there is a program that generates it and which is shorter than the string itself. We define the length of a program as the length of the shortest string of 0s and 1s that encodes that program.

A string is random if it is not reducible, i.e. if the shortest program that generates it is at least as long as the string itself (i.e. you cannot describe a string more concisely than simply stating it).

A finer analysis is: a string is additively k-reducible if there is a program that generates it and which is k shorter than the string itself, it is multiplicatively k-reducible if there is a program that generates it and which is k times shorter than the string itself, and it is strongly k-reducible if there is a program which generates it and which is shorter than k.

Since there are 1 + 2 + 2 *2 + 2 *3 + 2 *4+ … = 2 *n -1 < 2 *n strings shorter than n, it follows there are less than 2 *(n-k) strings shorter than n-k, there are less than 2 *(n/k) strings shorter than n/k and less than 2 *k strings shorter then k. Thus, the ratio of additive, multiplicative and strongly reducible strings to all strings is 2 *(n-k)/2 *n, 2 *(n/k)/2 *n and 2 *k/2 *n which is less than 0.001 for k>10. In short, a negligible number of strings is reducible in any of these meanings.

Imagine now a formalized theory (this can be ZFC in which we can formalize all existing mathematics) and in which we are proving the reducibility claims about strings (the statements of the form “string w can be generated by a program of length <,>,= n”) and the related program: Generate statements of that theory and check whether they are proofs of the statement “the string w cannot be generated by a program shorter than k+1” where k is the length of the shortest code of that program.

If that program stops on some string w then that string cannot be generated by a program shorter than k+1, but our theory which is a program of length k generates it, which is a contradiction. Thus, the formal theory of length k cannot prove that strings cannot be generated by programs shorter than k, if they really cannot be generated by them. But such are almost all strings because there are only finitely many of those that can be generated by programs shorter than k.

Thus, for no such string can we prove that it is irreducible even though almost all of them are. In other words, almost all such strings are random, although we cannot prove this for any of them.

Answer 1

Understanding randomness in terms of compressibility or entropy is fairly standard in information theory, but I don't believe it can be called philosophically satisfying. To achieve that, it would have to explain how 'random' is used in philosophical and scientific contexts.

'Random' is in practice a highly equivocal and confusing term. In ordinary usage, random means haphazard or capricious, having no definite aim, purpose, intention or plan. Typically, random is a negative term, implying an absence of an explanation, or at least an absence of any evidence of an explanation.

In the context of human action, an act is random if we can find no rational explation for it. If someone throws a brick through my window I might describe this as a random act of vandalism if I can discover no pattern or explanation for it, but I would not think of it as random if I suspected that it was an act of revenge by my neighbour for stealing his lawnmower. Note also that in neither case does random imply uncaused: there may be a perfectly good physical explanation for how the brick broke the window, but in the context of human action, this is largely irrelevant.

The meaning of random depends very much on the context.

1. Of human actions, random means having no rational explanation that we can discern.
2. Of natural phenomena, having no identifiable pattern, structure or predictability.
3. Of fundamental particles, having a behaviour that is irreducibly nondeterministic.
4. Of statistical data, that it is unbiased and has been collected in a way that is uncorrelated with the variables of interest.
5. Of a process, that it is stochastic and can be described only by a probability distribution.
6. Of a descriptive theory or model, that it allows for uncertainty because of incomplete information.
7. Of a belief, that it is based on little or no data.

These meanings diverge so much, it is not surprising that people confuse themselves when they talk about randomness.

Answer 2

Disclaimer: I am not a philosopher but a computer scientist.

First of all I think the definition of randomness seems fine. It resembles entropy, but is not equivalent. But thinking more about it it gets a little strange:

0000 for example is only considered not-random if I have a program of length 4 which generates this string. I can certainly have a programming language terse enough to express that, but you haven't fixed a language. Can I have a language that has my string as a constant somewhere? Is it Turing machines? Then I would expect I need a certain minimal length before anything is considered non-random, since I expect that Turing machines aren't very "efficient" in their encoding.

So I like the idea, it encapsulates well the aspect of randomness that there is no information in there that can be used to compress the string. I think it should also not be too big a surprise that there are more "random" strings than "non-random ones". The argument you are using is basically the pigeon-hole principle. If there are more strings of length k than n-k, then not all strings of length k can be expressed in n-k characters. It just so happens that every character adds an order of magnitude to the number of strings, so you arrive at the conclusion with 2^-k "non-random" string ratio.

What you have also shown is that a program of length k can't prove randomness of strings with length k+1. What does that help though? If a longer proof can tell me about the randomness is there a reason not to use it? Or is there reason to believe longer proofs don't exist?

Answer 3

Your proof is basically a recapitulation of the Turing Halting Problem / Godel Incompleteness Theorem / Berry Number Paradox. Your argument relies on the concept of "program" include your mathematical theory. And it doesn't prove that no number can be proved irreducible, it just shows that nonprovably irreducible sequences exist. Also, it doesn't fully correspond with what the term "random" means.