Reversibility
Tim Tyler
> "Tim Tyler" <t...@tt1lock.org> wrote in message news:HuA9F...@bath.ac.uk...
> > Hidde <Hidde...@hotmail.com> wrote or quoted:
> > > When I have a continious model (say Navier-Stokes equations) and I
> > > approach it numerically by using discrete space and time steps I
> > > will get numerical errors. If I am not careful about the numerical
> > > approximation the model is not stable and the small rounding errors
> > > will oscillate to very large errors.
> > >
> > > If true physics are also discrete, I would expect to find similar
> > > "errors" in the real world. [...]
> >
> > Cellular automaton models that simulate the Navier-Stokes equations exist.
> >
> > They do no rounding - and so are not prone to rounding errors.
> >
> > Instead they are exactly reversible - something rounding would normally
> > make impossible.
> >
> > E.g. see the FHP-model - as described on:
> >
> > http://poseidon.ulb.ac.be/simulations/intro_en.html
>
> It's amazing how our intuition fails us when it comes to discrete systems.
> The opinion expressed by Tim about exactly reversible systems, that
> "...rounding would normally make (the exactly reversible system)
> impossible." is believed to be true by almost everyone. However the
> statement is absolutely false. I and my students at MIT, 30 years ago,
> found the answers to almost every such question about the true nature of
> reversibility. Despite publishing all this, it's essentially lost art. I
> discovered a simple transform that takes a large class of digital
> computational process with or without roundoff and truncation error and
> converts them into very similar processes that are exactly reversible. By
> "similar" I mean that the differences are in the range of roundoff or
> truncation errors.
I /did/ say "normally".
*Usually* rounding errors destroy information - and result in
a system which is not reversible. This was very likely to be
the case for the OP's simulation.
It is certainly true that (e.g.) if the process being simulated
is already digital, then notes can be kept about the size of any
truncation errors (or other sources of information loss) - and
then this information can be systematically restored while
running the process in reverse.
--
__________
|im |yler http://timtyler.org/ t...@tt1lock.org Remove lock to reply.
Ed Fredkin
> Ed Fredkin <edfr...@yahoo.com> wrote or quoted:
> > "Tim Tyler" <t...@tt1lock.org> wrote in message news:HuA9F...@bath.ac.uk...
> > > Hidde <Hidde...@hotmail.com> wrote or quoted:
>
> > It's amazing how our intuition fails us when it comes to discrete systems.
> > The opinion expressed by Tim about exactly reversible systems, that
> > "...rounding would normally make (the exactly reversible system)
> > impossible." is believed to be true by almost everyone. However the
> > statement is absolutely false. I and my students at MIT, 30 years ago,
> > found the answers to almost every such question about the true nature of
> > reversibility. Despite publishing all this, it's essentially lost art. I
> > discovered a simple transform that takes a large class of digital
> > computational process with or without roundoff and truncation error and
> > converts them into very similar processes that are exactly reversible. By
> > "similar" I mean that the differences are in the range of roundoff or
> > truncation errors.
The trick is to convert the algorithm to be a 2nd order process
I have tried to make the example (below) clearer.
1. s[t+1] <= f(s[t])
f is any deterministic function that yields an integer, using either
roundoff or truncation.
We assume that there is an inexact inverse integer function g (inexact
because of different roundoff errors) such that
2. s[t-1] <= g(s[t]) We add the 2 "equations" to each other:
3. s[t+1]+s[t-1] = f(s[t])+g(s[t])
This is approximate if s[t-1] <= f(s[t-2]) (differing only by roundoff
errors)
4. s[t+1] <= f(s[t])+g(s[t])-s[t-1] This is the reversible forwards
equation that computes approximately the same s[t+1] as does eq 1.
You need to start it out with 2 initial values, s[t] and s[t-1].
5. s[t-1] <= f(s[t])+g(s[t])-s[t+1] This the reversible reversed
equation that computes the exact inverse of 4. despite roundoff or
truncation errors! You need to start it out properly with 2 initial
values, s[t] and s[t-1]
The easiest way to convince yourself is to program this up for
exponential
decay where f(x)=truncate(k*x) and g(x)=truncate((1/k)*x)
You can start eq 4. with k=0.9 s[t]=900, s[t-1]=1000 asuming
truncation
For eq 5. k=0.9 start off with 2 values s[n], s[n+1] computed by the
forward running of eq 4.
Ed F
>
> I /did/ say "normally".
>
> *Usually* rounding errors destroy information - and result in
> a system which is not reversible. This was very likely to be
> the case for the OP's simulation.
>
> It is certainly true that (e.g.) if the process being simulated
> is already digital, then notes can be kept about the size of any
> truncation errors (or other sources of information loss) - and
> then this information can be systematically restored while
> running the process in reverse.
Tim,
You still didn't get it, but in this case, it's my fault because the
previous example wasn't clear. I have tried to fix that here.
Systems with roundoff and truncation error can be perfectly (and
exactly) reversible, without paying any attention to the nature of the
roundoff, no notes need to be kept, no information needs to be
"restored" etc. That is why it is so unintuitive!
The only cure is to run or hand simulate the kind of software example
above. What happens is that the reversed process happens to generate
the same roundoff and truncation errors (since computers are
deterministic) in a way that undoes the errors introduced exactly and
automatically. Nothing needs to be done explicitly, all you have to
do is to run the little system quoted above (eq 4. ), in the forwards
direction, look at the values in the forwards direction, then,
starting with the last 2 values put into equation 5. run eq 5. to see
the process evolve in the reverse direction; esactly retracing its
steps.
If you're not amazed, it's just that I haven't explained it well
enough.
Ed F
Tim Tyler
> > I /did/ say "normally".
> >
> > *Usually* rounding errors destroy information - and result in
> > a system which is not reversible. This was very likely to be
> > the case for the OP's simulation.
> >
> > It is certainly true that (e.g.) if the process being simulated
> > is already digital, then notes can be kept about the size of any
> > truncation errors (or other sources of information loss) - and
> > then this information can be systematically restored while
> > running the process in reverse.
>
> Tim,
> You still didn't get it, but in this case, it's my fault because the
> previous example wasn't clear. I have tried to fix that here.
> Systems with roundoff and truncation error can be perfectly (and
> exactly) reversible, without paying any attention to the nature of the
> roundoff, no notes need to be kept, no information needs to be
> "restored" etc.
I agree - this is possible for some subset of input processes.
What I offered above was an *example* of a transformation fitting the
description you gave:
``a simple transform that takes a large class of digital computational
process with or without roundoff and truncation error and converts them
into very similar processes that are exactly reversible.''
Maybe my transformation was different from yours - but I fully expect
they both behave as described.
I did my best to indicate clearly that I was giving an example by using
"(e.g.)".
There are, of course, other ways of making reversible systems out of
irreversible ones besides the one I offered as an example.