monads and Turing machines

[José Manuel Rodríguez Caballero]

Below, I answer questions from Dennis Hamilton. I have listed the questions
in order of difficulty rather than in order of appearance.

Q1: the numbers in the registers, (in binary notation), are

> > initial condition:
> > ( )
> Or 0 ?
>

Yes, zero.


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

I meant 0 and 1/2 = 0.1


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

I meant 0, 1/2=0.1, 1/4 = 0.01, 3/4 = 0.11


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

I meant 0, 1/2=0.1, 1/4 = 0.01, 3/4 = 0.11, 1/8 = 0.01, 5/8 = 0.101, 3/8 =
0.011, 7/8 = 0.111

Q2:

> 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.
>

The numbers 1/3 and 1/5 are defined as cluster points. Indeed, the closed
interval of real numbers between 0 and 1 can be defined as the set of
cluster points associated with this computation.

Q3:

> > 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.


Consider a function f from the closed interval of real numbers between 0
and 1 to itself. For any element x in the closed interval between 0 and 1,
we can approximate this number as much as we want by a sequence of amoebas
generated by this computation. Now, inside each of these amoebas
approximating x, there is a sequence of amoebas approximating f(x) as much
as we want. Thus, such a function f is realized as a limiting process. Of
course, in most cases, the selection of such sequences is a non-computable
process.

I suspect that this monad-like Turing machine is related to the isomorphism
between the lightface and the boldface hierarchies [1]. That is, cluster
points of the computations, inside other computations, inside even more
computations, etc. are in correspondence to the way in which sets of points
are described in real analysis. So, I expect to find that this construction
is equivalent to some well-known classical method from effective
descriptive set theory [2] written in the language of Turing machines,
monads, and invoking the amoeba metaphor from quantum mechanics.

Kind regards,
Jose M.

[1] Moschovakis, Yiannis N. (1980). Descriptive Set Theory. North Holland.
ISBN 0-444-70199-0.

[2] Mansfield, Richard; Weitkamp, Galen (1985). Recursive Aspects of
Descriptive Set Theory. Oxford University Press. pp. 124–38. ISBN
978-0-19-503602-2. MR 0786122.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20230226/434f1dcd/attachment-0001.html>