monads and Turing machines

[dennis.hamilton at acm.org]

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