monads and Turing machines
dennis.hamilton at acm.org
dennis.hamilton at acm.org
Tue Feb 28 12:22:12 EST 2023
I have one observation about observed randomness. I will not pursue any of
the metaphysics (and ontological commitments).
From: José Manuel Rodríguez Caballero
Sent: Monday, February 27, 2023 23:56
Subject: Re: monads and Turing machines
> Using Hugh Everett's metaphor, the goal of a statistician Alice is to decide
> which amoeba she most likely lives in. Assuming eternity, the set of
> possible Alice's possible histories is uncountable, even if at any time
> there is only a finite set of amoebas.
I'm suspicious of that claim about uncountability, considering that at every
n-th generation there are 2^n possible states and they are always countable.
But continuing ...
> Zhang Yinsheng wrote:
> That is, randomness is non-Turing computable.
> Yes, but randomness can exist inside computational processes. Just write the
> numbers 1, 2, 3,... in binary code. This can be implemented using a Turing
> machine, but most of them will be random sequences of bits (except the first
> one from left to right, which is always 1). The question that I am
> addressing is how an observer, inside a computation, can perceive
> randomness.
Assuming a normalization that has all the states be of the same number (n) of
bits (including leading 0s), the challenge for Alice is the same - if the
state is revealed to her only one bit at a time, the probability of guessing
the next bit is 1/2, no matter how the sequence already observed might appear
random or non-random to Alice as a casual observer. If she's a typical
gambler, she may do worse, wanting to bet against randomness.
For an external observer, reaching into the morass of amoebae at cycle n, the
chance of guessing the state of one will be 1/2^n. Under the stated
conditions on the growth of n, it would be better to buy a lottery ticket ??.
Regards,
- Dennis
More information about the FOM
mailing list