I actually considered this in the case of reversing a Newton's iteration
a few years ago.
Consider, for example, reversing a Newton's iteration for the sqrt of a number.
Unfortunately, the commutativity of "+" loses 1 bit of information per iteration,
_even when we preserve infinite precision -- i.e., by starting with a rational
number and keeping rational numbers_ (e.g., do this with Macsyma/Maxima/Maple/etc.).
Thus, (x+N/x)/2 = (y+N/y)/2, where y=N/x, because N/y=N/(N/x)=x.
We will ignore this issue by making some sort of consistent choice. We now get
chaotic behavior -- even the smallest change in the initial conditions produces
very large changes in the succeeding computation.
But this is the whole point of the Newton iteration -- to eventually ignore the
initial "guess" and converge on the answer!
Thus, I concluded that convergence == reversed chaos!
At 10:28 AM 7/3/03 -0500, James Propp wrote:
>Most of us know (and if you don't already, you will by the end of this
>sentence!) that there are models of computation that are universal (they
>can simulate a Turing machine running an arbitrary program with arbitrary
>input) and also reversible (each state of the computation determines its
>predecessor).
>
>My question is, what happens if one uses reversibility to run a
>mathematically interesting computation into negative time?
>
>E.g., suppose one has a reversible machine that, when run forward, computes
>the sequence of primes, or the digits of pi, or something like that. Is
>there anything interesting that happens when you run the machine backwards?
>
>To make sense of this question, one needs to be precise about what it means
>to say that a machine computes something. Often there is some non-trivial
>representation scheme; e.g., in (non-reversible) Life-simulations, a sequence
>might be represented by the spacings of some gliders.
>
>It could be that if you run a computation backwards from zero, properties
>of the representation that hold at positive times cease to hold, so that
>there's no canonical way to extend the _representation_ of the computation
>as a sequence of digits or whatever.
>
>My guess is that for most interesting mathematical questions with answers
>indexed by the natural numbers, and for most reversible computation schemes
>for computing those answers, you don't get anything interesting or canonical
>by running the computation backwards. But it would still be interesting to
>see what happens if one tries.
>
>I should mention that one slight exception to my overall pessimism: namely,
>there are reversible (albeit non-universal) arithmetic models of computation
>which when run forward can compute good rational approximations to a
>quadratic irrational and when run in reverse compute good approximations
>to its algebraic conjugate. But this is a very special situation. And
>indeed, if one uses a similar model of computation to try to compute rational
>approximations to e, one finds that if one runs the program in reverse, it
>goes into an infinite loop when it tries to divide 1 by 0.
>
>Jim Propp
