1

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.

9
  • 1
    i think you're using the wrong symbol for an exponent. Oct 2 '20 at 16:22
  • I do not think a mathematical definition can help with clarifying philosophical status of randomness as a real phenomenon. There is already a canonical definition of random sequences based on computational complexity, see algorithmically random sequence, and the policy on this site is not to discuss users' own proposals.
    – Conifold
    Oct 2 '20 at 17:17
  • 2
    One thing that philosophers would probably not find acceptable is that you're essentially sketching the concept of Kolmogorov complexity but not stating this term outright — that makes it hard to relate your proposal to the existing literature.
    – Lars H
    Oct 2 '20 at 21:44
  • Randomness exists in Quantum Mechanics, and they've proved for certain that it is not due to "hidden variables"... it's genuinely probabalistic.
    – Almo
    Oct 2 '20 at 23:28
  • @Almo Can you clarify the nature of quantum randomness? Is it randomness of the events themselves? Or only of the measurements we can make of underlying events? And isn't the Schrödinger equation deterministic?
    – user4894
    Oct 3 '20 at 1:22
7

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.

6
  • Thanks, 1. -7. is helpful. Does 2. means that chaotic is random? Oct 2 '20 at 15:39
  • @ZvonimirSikic This is a great answer to your question. 'Random' in a philosophical sense must be much more explanatory than in a mathematical sense given the divergence of usages in different contexts. As for chaotic in the mathematical sense, deterministic mathematical laws are in play, so strictly speaking, chaotic behavior of systems, such as those of strange attractors, straddles the border between the predictability of geometric sequences and true mathematical randomness. One of the goals of naturalism is to see the forest for the trees.
    – J D
    Oct 2 '20 at 15:53
  • Isn't 3 an example of 2? It reads the same just with deterministic being synonymous with predictable. 5 too.
    – Cell
    Oct 2 '20 at 16:18
  • Chaotic systems are deterministic but also unpredictable. If pushed I would say a chaotic system is not truly random, but it is common to describe systems that are unpredictable in principle as random. For example, in statistical mechanics one might commonly say that the motion of molecules of gas is random since it is infeasible to describe them using anything other than a statistical distribution. 3 is different, since what I have in mind there is quantum indeterminacy. 5 can differ from 2, because we can distinguish between a random process and a random product.
    – Bumble
    Oct 2 '20 at 17:50
  • Cell; Not really, deterministic chaos falls into the 2nd but does not fall into the 3rd. Oct 3 '20 at 11:08
1

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?

3
  • 1
    "Enumerate all programs of length <= k and check whether they generate w. " That doesn't work: some programs won't halt, and you can't tell which ones will. Oct 2 '20 at 14:13
  • @NoahSchweber That's... right unfortunately. I'll delete that part of the answer.
    – kutschkem
    Oct 2 '20 at 15:25
  • Kutschkem says „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? “ But it is is not a problem of short and long proofs. Theory of length k (e.g. ZFC) may have proofs of any length and neither of them is a proof of randomness of strings with length k+1. This is just a version of Chaitin incompleteness theorem. Oct 2 '20 at 15:57
1

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.

1
  • This is actually a Chaitin incompleteness theorem, as I mentioned in one of the comments above, and they are of course related to everything you mention. Oct 3 '20 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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