The Dynamics of Impossible Devices

Ian Stewart

'Sometimes I've believed as many as six impossible things before breakfast.' Lewis Carroll,Through the Looking Glass

Mathematical models have the capacity to represent not only all possible worlds, but most impossible ones as well.For example Maurits Escher's perpetually circulating 'Waterfall' can easily be modelled by a flow in a solid torus, or perhaps its cartesian product with a circle (to model the waterwheel as well).Gerver [5] and Xia [12] have proved that systems of point masses under Newtonian gravitation can hurl themselves off to infinity in a finite period of time.

Roger Penrose's The Emperor's New Mind [7] has as its central thesis the idea that nature produces harnessable noncomputable processes, but at the quantum level only. He goes on to suggest that human intelligence may be an example, and that philosophical puzzles such as free will might thereby be resolved. We here pursue the paradoxical ability of classical mechanical systems to model impossible processes, and suggest that it bears not only upon Penrose's Thesis, but also upon the general question of computability in dynamical systems.

A number of recent papers have addressed both issues. Using a model of the computational process in which exact real arithmetic is possible, Blum, Shub, and Smale [2] prove that Julia sets - and, assuming a plausible conjecture in complex analysis, the Mandelbrot set itself - are uncomputable. (This is somewhat ironic when the walls of the planet are papered with computer graphics of Mandelbrot sets.) Moore [6] gives an example of a deterministic system whose trajectories are not just chaotic, but uncomputable. Rather earlier, Scarpellini [8] remarked that it may be possible "to build an analog computer that can simulate functions f(x) so that the predicate [ (f(x))] isn't decidable, while the analog machine itself decides it." Inspired by this remark, da Costa and Doria [4] explore the limits of computability in chaotic classical dynamical systems, and cast serious doubt [3] upon Penrose's Thesis. They demonstrate the formal undecidability of many basic questions in dynamical systems theory: whether a horseshoe exists, whether the dynamics is chaotic; whether a trajectory starting from a given initial point eventually passes through some specific region of phase space; whether the equations are integrable. Indeed virtually any interesting question about dynamical systems is undecidable.This is not to assert that such questions cannot be answered for specific systems: for example M.Benedicks and L.Carleson [1] prove that for a set of parameter values of nonzero measure the Hénon system possesses chaotic attractors. Their results do not seem to lead to explicit parameter values at which chaos occurs, but that is probably not relevant to the present discussion.

On thinking about these matters, it becomes clear that dynamical systems possess strong undecidability properties because they are sufficiently versatile that they can model the computational process itself. My claim is that they are far more versatile, enough so to become paradoxical. The foundations for this contention were laid some years ago when I contributed to a special issue of Pour La Science on 'large computer systems'. Knowing nothing about such things, I took an extreme view and considered infinite computer systems [9,10,11]. Some infinities are relatively harmless: for example, Turing permits his eponymous machines to possess infinite memories, a perfectly conventional assumption in theoretical computer science. Less conventional is the Rapidly Accelerating Computer (RAC) whose clock accelerates exponentially fast, with pulses at (say) times 1-2-n as n tends to infinity. RAC can cram an infinite number of computations into a single second.It is indifferent to the algorithmic complexity of the task set to it: everything runs, not in exponential or polynomial time, but in bounded time.It can therefore solve the halting problem for Turing machines (which Turing proved algorithmically undecidable) by running a computation in accelerating time and throwing a particular switch if and only if the Turing machine halts. Like all computations carried out by RAC, the entire procedure is completed within one second: it is then sufficient to inspect the switch to see whether it has been thrown.

RAC can calculate the incaculable. It can prove or disprove Fermat's Last Theorem by checking all possible cases. It can prove or disprove the Riemann hypothesis by computing all zeros of the zeta function. More ambitiously, it can run a computation that will prove all possible theorems in its Industry Standard Second, by pursuing all logically valid chains of deduction from the axioms of set theory. RAC is also impossible in the real world.

However, it appears to be entirely possible within classical mechanics. We can model it by a classical (that is non-quantum) dynamical system. Indeed there are several ways to achieve this: as a Turing machine whose tape-movement accelerates exponentially, as a ball-bearing computer with balls that speed up like the point masses in the work of Xia and Gerver, or as idealised but realistic equations for the electronic components of a computer with infinite memory. (PDEs rather than ODEs seem in order here, and it is best to use the 'Golden RAM', based on an infinitely fine subdisivison of a golden rectangle into squares of ever-decreasing size, which provides infinitely many MB in a finite space.)

Because classical mechanics poses no upper bound upon velocities, it is possible to 'accelerate' time in these equations merely by reparametrizing it, so that infinite 'subjective' time passes within a finite period of 'objective' time. By simultaneously compressing space, if necessary, we can ensure adequate smoothness of the equations, and continue at least the relevant motions past the One Second Singularity. That a singularity exists seems to pose no serious philosophical or conceptual problems, given that the same is true of Newtonian gravitation. Thus we have a system of classical equations which mimics the operations of RAC: accordingly, the dynamics of that system can compute the uncomputable, decide the undecidable, complete the incompletable, and generally possibilify the impossible.

On this basis it seems a reasonable conjecture that a suitable system of point masses, obeying Newtonian gravitation, can also simulate RAC. You could hardly get more classical!

Be that as it may, we conclude that if Penrose's thesis has any chance of being valid, then it must be posed for 'real' classical systems rather than mathematical ones - a somewhat paradoxical concept in a world that is 'really' quantum. For example, one might insist that velocities are bounded from above, and masses, distances and intervals of time from below. Care must then be taken to ensure that in avoiding some of Zeno's paradoxes, one has not blundered into the others. Bertrand Russell was forced to make similar assumptions when discussing the nature of causality. Clearly some rethinking is in order here - quite possibly by me. Until the entire pipedream falls apart, the new science of akatorthotology - the study of the impossible - seems to be off to an excellent start. The White Queen, at least, would approve.

REFERENCES

  1. M.Benedicks and L.Carleson, Ann. of Math. 133 (1991) 73-169.
  2. L.Blum, M.Shub., and S.Smale, Bull. Amer. Math. Soc. 21 (1989) 1-46.
  3. N.C.A.da Costa and F.A.Doria, Classical Physics and Penrose's Thesis, preprint, Institute for Advanced Studies, University of São Paulo; to appear in Foundations of Phys. Lett.
  4. N.C.A.da Costa and F.A.Doria, Undecidability and Incompleteness in Classical Mechanics, preprint, Institute for Advanced Studies, University of São Paulo, to appear in Internat. J. Theor. Phys.
  5. J.Gerver, The existence of pseudocollisions in the plane, preprint, Rutgers U 1990, to appear in J. Diff. Eq.
  6. C.Moore, Physics Review Letters 64 (1990) 2354.
  7. R.Penrose, The Emperor's New Mind, Oxford University Press, Oxford 1990.
  8. B.Scarpellini, Z. Math. Log. Grundl. Math. 9 (1963) 265.
  9. I.N.Stewart, Les Fractals, Librairie Classique Eugène Belin, Paris 1982.
  10. I.N.Stewart, Le Laboratoire d'Infinormatique de Z. Bunnydew, Pour La Science 122 (1987) 160-164.
  11. I.N.Stewart, Game, Set, and Math, Penguin Books, Harmondsworth 1991.
  12. Z.Xia, On the existence of non-collision singularities in Newtonian n body systems, doctoral dissertation, Northwestern U 1988.