monads and Turing machines
dennis.hamilton at acm.org
dennis.hamilton at acm.org
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?
Regards,
- Dennis
More information about the FOM
mailing list