true randomness in mathematics

Thu Mar 17 12:40:54 EDT 2022

Best, Jan Pax wrote:

> Hi
> do you mean here
> a sequence of bits x_1, x_2, x_3, ... is pseudo-random if and only if the
> Kolmogorov complexity of x_n is a logarithmic function of n for almost all
> values of n.
> or rather
> (x_1, x_2, x_3, ...,x_n)

You are right if we interpret each x_n as a single bit. Maybe I used rather
ambiguous language. By a sequence of bits I meant that each x_n is a finite
sequence of bits, like x_3 = 0010101. In this case, the complexity of x_n
is the length of the shortest program for generating x_n (up to a fixed
constant). That was the definition I used in my preprint:
https://arxiv.org/pdf/2108.03751.pdf

" For the aperiodic case, for all n large enough, the descriptive
complexity of x_n is equal to a constant plus the number of binary digits
of n [for almost all values of n, not all values]".

Kind regards,
Jose M.

On Thu, Mar 17, 2022 at 8:00 AM <pax0 at seznam.cz> wrote:

> Hi
> do you mean here
> a sequence of bits x_1, x_2, x_3, ... is pseudo-random if and only if the
> Kolmogorov complexity of x_n is a logarithmic function of n for almost all
> values of n.
>
> or rather
>
> (x_1, x_2, x_3, ...,x_n)
> ?
>
> This is beacuse a signle bit has a constant complexity.
>
> Best, Jan Pax
>
> Thomas Klimpel wrote:
>
> Such a distinction between true randomness and pseudo-randomness
> appears to me to depend on interpretative assumptions. In my opinion,
> mathematical existence gains relevance by describing idealizations of
> real life situations. Describing which idealized properties true
> randomness should have in such real life situations then allows us to
> accept more sources of randomness than just those based on quantum
> randomness.
>
>
> In your reference you provide two definitions of true randomness:
>
>
>    - *Quantum mechanics*: The *randomness *itself is nonlocal, and it
>    must be *really random*, because otherwise this non-locality could be
>    used for instantaneous signal transmission.
>    - *Gambling and games*: A *truly random phenomenon* must produce
>    outcomes that are completely unpredictable. And not just unpredictable for
>    you and me, but unpredictable for both my opponents and proponents.
>
>
> https://gentzen.wordpress.com/2022/02/28/true-randomness-and-ontological-commitments/
>
> For the "Quantum mechanics" definition above, I do not use anything
> physical, except the hypothesis that the universes branches after quantum
> measurements, i.e., just a tree from graph theory:
>
> Everett, Hugh. "The theory of the universal wave function." The
> many-worlds interpretation of quantum mechanics. Princeton University
> Press, 2015. 1-140.
> https://www.pbs.org/wgbh/nova/manyworlds/pdf/dissertation.pdf
>
>  My definition of true randomness is grounded on the theory of
> computability and algorithmic information theory:
>
> Given a black box generating a sequence of bits, i.e., 0s or 1s, x_1, x_2,
> x_3, ..., we say that this black box is pseudo-random if there is a
> (deterministic) algorithm generating the same sequence of numbers. If this
> is not the case, we say that this black box is truly random.
>
> A characterization of true randomness using the Kolmogorov complexity and
> the notion of time is as follows:
>
> (i) a sequence of bits x_1, x_2, x_3, ... is pseudo-random if and only if
> the Kolmogorov complexity of x_n is a logarithmic function of n for almost
> all values of n.
>
> (ii) a sequence of bits x_1, x_2, x_3, ... is truly-random if and only if
> the Kolmogorov complexity of x_n is a linear function of n for almost all
> values of n.
>
> Notice that "Gambling and games" definition above can be a case of
> pseudo-randomness, where the unpredictability is given by
> complexity-theoretic bounds. This is what is used in complexity-theoretic
> cryptography.
>
> There are some results about extracting true randomness from big data
>
> https://www.nature.com/articles/srep33740
>
> but we need to consider the fact that we live in a world where random
> events triggered by quantum mechanics happen all the time. These events are
> amplified by the butterfly effect:
>
> https://www.wikiwand.com/en/Butterfly_effect
>
> I am not aware of a source of true randomness other than quantum
> mechanics: all other sources of true randomness may rely on quantum
> phenomena at the fundamental level.
>
> The fact that quantum mechanics is a source of true randomness seems to be
> a consequence of the Copernican principle. Indeed, considering the
> branching of the universe after quantum measurements, most positions will
> be truly random just because of combinatorics. In virtue of the Copernican
> principle, we should be in a branch that is not special, i.e., a random
> branch. Therefore the randomness of quantum mechanics is just a consequence
> of the fact that we are at a random position in the branching of the
> universe.
>
> Whether true randomness plays a role in the development of mathematics can
> be experimentally checked by developing two scholastic simulations of the
> work of a mathematician. One simulation should use a pseudo-random bit
> generator and the other one, a quantum random bit generator. Comparing the
> performance of these simulations with the empirical data about how
> mathematics was historically developed may show some statistical
> differences.
>
> As far as I know, there are no results comparing the efficiency of
> automatic theorem provers using pseudo-random generators and truly random
> generators, using the definition of Kolmogorov complexity. It would be
> interesting to know whether the results are universal (for all theories) or
> specific (for some theories pseudo-randomness and true randomness are
> equally efficient, but for other theories, true randomness is more
> efficient).
>
> Kind regards,
> Jose M.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20220317/01e38fa1/attachment.html>