monads and Turing machines

dennis.hamilton at dennis.hamilton at
Sun Feb 26 12:59:04 EST 2023

I am having some difficult with the described constructions and one of the 
claims.  I will abridge the post to focus on the passages that have 
difficulties for me.

From: José Manuel Rodríguez Caballero
Sent: Sunday, February 26, 2023 00:02
Subject: monads and Turing machines

Dear FOM members,

> Initially, there is only one amoeba and its register is empty, representing 
> the zero. During the n-th iteration, the Turing machine produces a copy of 
> all the existing amoebas, the only difference being that the registers of 
> the new amoebas are increased by 1 over 2 to the power n

Is it the case that this is a notation for binary fractions and you mean there 
is one more bit to the right (i.e., bit n corresponds to weight 1/2^n?  In 
effect, at each cycle, is it the case that there are 2^n amoebas and their 
registers effectively enumerate the integers from 0 to 2^n-1, Standing for the 
reciprocals of the non-zero values?

> initial condition:
> ( )
Or 0 ?

> after the first iteration
> ( ) (1)
Or 0,1 ?

> after the second iteration
( ) (1) (01) (11)
Or 00, 10, 01, 11 ?

> after the third iteration
( ) (1) (01) (11) (001) (101) (011) (111)
Or 000, 100, 010, 110, 001, 101, 011, 111 ?

> etc.

It seems here that you are simply omitting trailing zeroes, although that 
would not alter the situation.

> One can defend the thesis that this computation defines the set of functions 
> of the closed interval between 0 and 1 to itself, which has a cardinality 
> strictly greater than the cardinality of the set of real numbers.

It is not clear to me that this claim is defensible.  First, denumerability 
has not been escaped, so it is unclear how a non-denumerable set of functions 
have been represented.

In fact, this scheme doesn't even enumerate all of the rationals in the 
interval [0,1], considering incommensurate prime denominators.  For example, 
1/3 and 1/5 are not captured in this sequence.  There are repairs for this, 
but they don't extend the cardinality beyond the denumerable.

How have I misunderstood the construction?


 - Dennis

More information about the FOM mailing list