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.

Zvonimir Sikic
  • 19
  • 2
  • 1
    i think you're using the wrong symbol for an exponent. – robert bristow-johnson Oct 02 '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](https://en.wikipedia.org/wiki/Algorithmically_random_sequence), and the policy on this site is not to discuss users' own proposals. – Conifold Oct 02 '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](https://en.wikipedia.org/wiki/Kolmogorov_complexity) but not stating this term outright — that makes it hard to relate your proposal to the existing literature. – Lars H Oct 02 '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 02 '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 03 '20 at 01:22
  • robert bristow-johnson, sorry, there is no cap symbols on my keyboard (or I am not finding them) – Zvonimir Sikic Oct 03 '20 at 10:58
  • Lars H., I agree, my motivation for not mentioning it was not to open up questions of priority, accurate presentation, etc. but you are right. – Zvonimir Sikic Oct 03 '20 at 11:05
  • The events themselves are probabilistic. And it is proven that they are not deterministic if we could measure something inside; that’s what I mean by “hidden variables has been disproven”. At a fundamental level, actual randomness is built into the fabric of the universe. I can’t explain it all here, but here’s a starting point: https://scienceworld.wolfram.com/physics/HiddenVariables.html – Almo Oct 03 '20 at 15:37
  • *"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"* This isn't especially meaningful unless you put some constraints on what the program can be. We can define an infinite class of languages *L(s)*, under which the program consisting only of the bit 0 outputs *s*, and any program that starts with the bit 1 is interpreted by removing the leading 1 and interpreting the remainder as though it were a C program. Thus for *every* string *s* of length k bits, there is a language *L(s)* under which *s* is (k-1)-reducible – Ray Oct 05 '20 at 03:56

3 Answers3

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.

Bumble
  • 20,757
  • 2
  • 27
  • 65
  • Thanks, 1. -7. is helpful. Does 2. means that chaotic is random? – Zvonimir Sikic Oct 02 '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](https://en.wikipedia.org/wiki/Chaos_theory) 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 02 '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 02 '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 02 '20 at 17:50
  • Cell; Not really, deterministic chaos falls into the 2nd but does not fall into the 3rd. – Zvonimir Sikic Oct 03 '20 at 11:08
  • There is no mention of chaos in any of those definitions. Also there are physical systems that are not quantum related that are deterministically chaotic. – Cell Oct 03 '20 at 11:31
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?

kutschkem
  • 2,172
  • 10
  • 17
  • 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](https://en.wikipedia.org/wiki/Halting_problem). – Noah Schweber Oct 02 '20 at 14:13
  • @NoahSchweber That's... right unfortunately. I'll delete that part of the answer. – kutschkem Oct 02 '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. – Zvonimir Sikic Oct 02 '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.

Acccumulation
  • 921
  • 4
  • 11
  • 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. – Zvonimir Sikic Oct 03 '20 at 11:13