FOM: CAs as mappings from reals to reals vznuri at
Tue Aug 13 16:17:07 EDT 2002

hi all. I havent seen this proposed yet, although
Im not totally up on the vast CA literature.. (who is??)

this just occurred to me after chatting with JB in
a sort of lakatos-style "proofs and refutations" dialogue we're
having in email.  looks like a very fruitful way of looking at CAs.

a CA can be seen as a simple mapping of reals to reals!!
just take the states as digits of a fractional number. 
maybe the simplest way to see it is taking the "decimal" place
to precide the leftmost digit, therefore a mapping from
{0-1} -> {0->1}

(what is the name for a "decimal" place in different bases?
I am thinking of generalized bases here, such that the base
matches the number of states.)

the mapping then just replaces digits of the input based on the
"local neighbor" rule.

now.. a question for the audience: is there a name for this distinct
mapping from reals to reals somewhere in the literature?? it seems
very obscure & novel, but given how vast the literature is, one can never
be sure.

also it leads me to immediately wonder about fixed points of
the mapping. considering fixed points of mappings almost always leads to
very deep theorems in math.

and hey!! think about it!! cantors diagonalization argument
for reals then is simply the rule 0->1, 1->0 applied to an 
arbitrary real on the input (given in binary form). diagonalization
as a primitive CA rule!!

this idea popped up after I started talking about a 
1-2-3-.. type pattern as an input to a CA in addressing
one of our conjectures/inquiries into computational universality.

a 1-2-3-.. type pattern would be something like
1101001000100001.. as one instance, although defineed as
generally as possible.

such a construction is interesting because it is one of the
simplest nonperiodic constructions. I was using it in a half-baked

also in thinking about this, it looks like rationals, algebraic and
transcendental numbers etcetera correspond to classes of CA

another interesting idea. suppose that you wish to define a mapping
from complex numbers to complex numbers. one could just look at
alternating digits of the CA as the real and complex digits.

also one can start to see the tieins with kolmogorov
complexity.  in fact I wonder if all the results on chaitins
omega function etcetera could be easier or more fundamentally
described in terms
of CAs....!!

hey, please forgive me, but I think this is all very deep & will
lead to something very interesting. its amazing how much existing
mathematics frameworks can be linked up to CAs. it really makes
me wonder if the whole field of mathematics will go through
a phase change w.r.t CAs. it looks quite plausible to me.

More information about the FOM mailing list