reversible universal 1D CA?
IzI
Reversible:
A specially constructed rule to be reversible using second order, cell
block or some other technique.
Universal:
Is able to simulate other CA, the neighborhood size may be limited but
the number of cell value should be unlimited (big neighborhoods can be
transformed into multivalued cells).
IzI
Tim Tyler
You can use the "second order technique" to make any CA into a
reversible CA - by doubling the volume of its state.
See http://cell-auto.com/design/ for details of the technique.
Since we know of universal 1D CA, we can therefore pretty easily
construct universal *reversible* 1D CA from them.
--
__________
|im |yler http://timtyler.org/ t...@tt1lock.org Remove lock to reply.
Ilmari Karonen
>
> You can use the "second order technique" to make any CA into a
> reversible CA - by doubling the volume of its state.
>
> See http://cell-auto.com/design/ for details of the technique.
>
> Since we know of universal 1D CA, we can therefore pretty easily
> construct universal *reversible* 1D CA from them.
Is that really true? The behavior of second order rules is usually
quite different from the first order rules they are based on. So I
don't see how the universality of a particular rule would imply that
the corresponding second order rule is also universal.
--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
Tim Tyler
> Tim Tyler <t...@tt1lock.org> kirjoitti 07.09.2005:
> > You can use the "second order technique" to make any CA into a
> > reversible CA - by doubling the volume of its state.
> >
> > See http://cell-auto.com/design/ for details of the technique.
> >
> > Since we know of universal 1D CA, we can therefore pretty easily
> > construct universal *reversible* 1D CA from them.
>
> Is that really true? The behavior of second order rules is usually
> quite different from the first order rules they are based on. So I
> don't see how the universality of a particular rule would imply that
> the corresponding second order rule is also universal.
Your scepticism appears justified - I don't know of a convincing
reason to think this either.
In that case, the best demonstration I can think of the existence of
a 1D reversible universal CA derives from the observation that there
are reversible TMs - i.e. see:
``Charles Bennett, ``Logical Reversibility of Computation'', IBM Journal
of Research and Development, Vol. 17, 1973, pp. 525-532''
This involves multiple tapes moving at different speeds - so a map to
a 1DCA is not exactly obvious; but it could be done - by mapping the
multiple tapes onto multiple "layers".
While I haven't looked closely at this construction, it appears to be
broadly equivalent to the method of generating reversibility involving
embedding an n dimensional automation in an n+1 dimensional one
(as mentioned on the above URL): though instead of storing the
history of the system in the additional dimension, it instead stores
it in a continuously-moving "history tape".
If that's accurate, then the construction is likely to compute
rather slowly and inefficiently - since it effectively has to write
the state of the automaton to the history tape on each update of the
main tape - and that operation is likely to take longer and longer as
the computation progresses.
IzI
there are some interesting papers by Kenichi Morita
http://www.iec.hiroshima-u.ac.jp/~morita/pub2.html
IzI
Tim Tyler
> just for the record
>
> there are some interesting papers by Kenichi Morita
> http://www.iec.hiroshima-u.ac.jp/~morita/pub2.html
Indeed. The automaton in:
``Reversible Simulation of One-Dimensional Irreversible Cellular Automata''
- http://www.ke.sys.hiroshima-u.ac.jp/~morita/1995/Mor95.htm
...appears to have the same properties as the construction I mentioned -
in that it also deals with the case of one-dimensional CA with finite
initial configurations.
Siamak
> ``Reversible Simulation of One-Dimensional Irreversible Cellular Automata''
>
> - http://www.ke.sys.hiroshima-u.ac.jp/~morita/1995/Mor95.htm
Of course this simulates other CA only on finite configurations, which
essentially is not so different from simulating Turing machines. Note
also that the simulation is not in real time. I suspect there is no 1d
reversible CA which is really intrinsically universal.
Siamak
Tim Tyler
> Tim Tyler wrote:
There are 1D reversible CA that can do everything a Turing machine can do.
I'm not sure exactly what you mean by "intrinsically universal".
Perhaps you are referring to the ability to receive an infinite number
of simultaneous inputs, process them in a finite time - and continue to
do that indefinitely?
If so, you may be right. In general, no reversible CA can continue to
receive arbitrary inputs indefinitely - without eventually "filling up".
Tim Tyler
That last statement isn't true - it's only 1D systems that really have
this problem, since they have no spare dimensions to dispose of their
waste products in.
I see what you mean: it looks like a 1D reversible CA is only as powerful
as a TM.
I.e. it can't process infinite inputs indefinitely - like most other
universal cellular automata can. Interesting.
Siamak
> There are 1D reversible CA that can do everything a Turing machine can do.
>
> I'm not sure exactly what you mean by "intrinsically universal".
That is, given a CA F, we could `encode' any initial configuration (not
necessarily finite) into a configuration of the universal CA U, and we
could `decode' the configuration at time t of F from configuration at
time kt (k depends on F) of U. Like, mapping every cell in F, to a
block of cells in U, and look at that block every k steps ...
Ollinger's [ICALP'2002] paper defines it precisely:
http://www.lif.univ-mrs.fr/~nollinge/publis/
> In general, no reversible CA can continue to
> receive arbitrary inputs indefinitely - without eventually "filling up".
I guess you must be right. Perhaps there can be found some 1d
irreversible CA which cannot be simulated (in the above sense) by any
1d reversible CA.
Siamak
Guillaume THEYSSIER
> Ollinger's [ICALP'2002] paper defines it precisely:
> http://www.lif.univ-mrs.fr/~nollinge/publis/
>
>
> I guess you must be right. Perhaps there can be found some 1d
> irreversible CA which cannot be simulated (in the above sense) by any
> 1d reversible CA.
Following Ollinger's definition of "simulation" and using the classical
result of Moore-Myhill about surjective (onto) CA, one can prouve that a
surjective CA can only simulate surjective CA. The same is true with
reversible (one-to-one) CA : a reversible CA can never simulate an
irreversible one.
So there is no intrinsically universal CA which is reversible.
Guillaume
Tim Tyler
> Siamak a écrit :
> > Ollinger's [ICALP'2002] paper defines it precisely:
> > http://www.lif.univ-mrs.fr/~nollinge/publis/
[...]
> Following Ollinger's definition of "simulation" and using the classical
> result of Moore-Myhill about surjective (onto) CA, one can prouve that a
> surjective CA can only simulate surjective CA. The same is true with
> reversible (one-to-one) CA : a reversible CA can never simulate an
> irreversible one.
> So there is no intrinsically universal CA which is reversible.
Lots of universal reversible CA are known - e.g. the billiard ball
machine.
It isn't accurate that a reversible CA can never simulate an
irreversible one: every irreversible CA can be simulated by
a reversible one - and a simple construction produces such
a reversible CA from an irreversible one.
I'm not sure what you are getting at with the phrase
"intrinsically universal".
Guillaume THEYSSIER
> "intrinsically universal".
Each cell is simulated by a block of cells (one-to-one correspondance)
and each step is simulated in a constant number of steps. See Ollinger's
paper for a formal definition. With that precise definition there is no
reversible universal CA.
I'm not saying that this is THE definition of universality but it is
very natural and perfectly formalized. It is "intrinsical" because it
deals only with CA (no turing machines).
> It isn't accurate that a reversible CA can never simulate an
> irreversible one: every irreversible CA can be simulated by
> a reversible one
So it isn't accurate... :-)
>- and a simple construction produces such
> a reversible CA from an irreversible one.
Ok, it's a matter of definition of "simulation". Can you give a formal
definition of simulation which makes your statement true.
Guillaume
Tim Tyler
> > I'm not sure what you are getting at with the phrase
> > "intrinsically universal".
I see "intrinsically universal" is a term discussed by Ollinger - on:
http://www.lif.univ-mrs.fr/~nollinge/publis/publis-abstracts.html
> Each cell is simulated by a block of cells (one-to-one correspondance)
> and each step is simulated in a constant number of steps. See Ollinger's
> paper for a formal definition. With that precise definition there is no
> reversible universal CA.
Where are you getting that conclusion from?
Ollinger's papers are mostly about one dimensional cellular automata.
Have you perhaps missed out a "one dimensional" qualification in the
above claim?
Also note that "intrinsically universal" does not have the same meaning as
the term "universal". Above, you mention "universal CA" - but your
reference seems concerned with "intrinsic universality" - which is
a different property.
> >- and a simple construction produces such
> > a reversible CA from an irreversible one.
>
> Ok, it's a matter of definition of "simulation". Can you give a formal
> definition of simulation which makes your statement true.
On reflection, I don't think this is a difference in definition of
the term simulation.
Ollinger proposes a specific sense of the term in connection with cellular
automata - which seems to go a bit beyond the notion of one machine being
said to simulate another machine if it can reproduce its outputs from a
specified set of inputs - but I don't think that's the issue: even in
Ollinger's sense of the term simulation you can construct a reversible
CA that simulates any specified irreversible one.
What it appears that you can't construct is a reversible *1D* CA
that does that.
Siamak
I guess when Guillaume said universal he meant Ollinger's intrinsic
universality (as opposed to Turing universality or whatever), and he
has mentioned it at the very beginning of his post. He's also talking
about 1d CA as the previous posts were mainly about 1d CA, but his
statement is also true for higher dimensions, which means that for
example 2d non-surjective CA cannot be simulated (in Ollinger's sense)
by any 2d surjective CA, and so on.
Of course, Toffoli has formerly shown that any d-dimensional CA can be
simulated (in a natural sense) by a (d+1)-dimensional reversible CA.
Anyway, I think what Guillaume has pointed out reveals a deficiency in
Ollinger's definition. For example, it's sort of weird that the
trivial 1d-CA that turns every state into 0 cannot be simulated by any
surjective 1d-CA. In my opinion a good notion of simulation should
include an irreversible observation layer. Perhaps we can define it
this way: let's say a d-dimensional CA with global map G simulates a
d-dimensional CA with global map F, if there are mappings P and Q and a
constant k, so that
F = Q o G^k o P
where P and Q may include rescalings as well as irreversible local
transformations.
Still with this definition, I suspect no reversible 1d-CA exists that
can universally simulate every other 1d-CA.
Siamak
Guillaume THEYSSIER
> Tim,
> I guess when Guillaume said universal he meant Ollinger's intrinsic
> universality (as opposed to Turing universality or whatever), and he
> has mentioned it at the very beginning of his post. He's also talking
> about 1d CA as the previous posts were mainly about 1d CA, but his
> statement is also true for higher dimensions, which means that for
> example 2d non-surjective CA cannot be simulated (in Ollinger's sense)
> by any 2d surjective CA, and so on.
Yes. I admit it was not clear enough.
> In my opinion a good notion of simulation should
> include an irreversible observation layer. Perhaps we can define it
> this way: let's say a d-dimensional CA with global map G simulates a
> d-dimensional CA with global map F, if there are mappings P and Q and a
> constant k, so that
> F = Q o G^k o P
> where P and Q may include rescalings as well as irreversible local
> transformations.
Interesting, but what do you mean precisely by "irreversible local
tranformations"?
Guillaume
Siamak
> > F = Q o G^k o P
> > where P and Q may include rescalings as well as irreversible local
> > transformations.
>
> Interesting, but what do you mean precisely by "irreversible local
> tranformations"?
Well, I just meant a local mapping (like that of a CA) from
configurations with cell-state-set T to configurations with
cell-state-set S, which is not necessarily injective.
That is, for example in 1d case, the mapping Q
- First groups the cells into blocks of length m, and obtains a
configuration with state set T
- Then it applies a local rule on each cell to obtain a
configuration with state set S. (This might be irreversible.)
- Finally, it de-groups each cell into a block of length n of cells.
IMO, irreversibility is important when it comes to simulation. It's
like, we need to wear a glass through which the behaivior of machine M1
looks like the actual behavior of machine M2.
Now, this way, is it possible to simulate any 1d-CA by a reversible
one?
Siamak
Guillaume THEYSSIER
> That is, for example in 1d case, the mapping Q
> - First groups the cells into blocks of length m, and obtains a
> configuration with state set T
> - Then it applies a local rule on each cell to obtain a
> configuration with state set S. (This might be irreversible.)
> - Finally, it de-groups each cell into a block of length n of cells.
> Now, this way, is it possible to simulate any 1d-CA by a reversible
> one?
Yes! The identity CA over {0,1} is universal...
Too much power is allowed in the coding/decoding mechanism with your
notion of simulation.
Siamak
> Yes! The identity CA over {0,1} is universal...
Ah! As usual I was careless ...
I wrote:
> F = Q o G^k o P
I meant:
F^t = Q o G^kt o P
for all t.
This made no difference in Ollinger's definition because there P*Q was
just a shift.
Siamak
Siamak
> Too much power is allowed in the coding/decoding
> mechanism with your notion of simulation.
Sorry! You are right. My definition just doesn't make sense, unless we
put some more restriction on P and Q.
Siamak