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