Notes

Chapter 12: The Principle of Computational Equivalence

Section 4: The Validity of the Principle


Emulating discrete systems [with continuous ones]

Despite it often being assumed that continuous systems are computationally more sophisticated than discrete ones, it has in practice proved surprisingly difficult to make continuous systems emulate discrete ones. Some integer functions can readily be obtained by supplying integer arguments to continuous functions, so that for example Mod[x, 2] corresponds to Sin[Pi x/2]^2 or (1-Cos[Pi x])/2,

Mod[x, 3] ↔ 1 + 2/3(Cos[2 Pi (x - 2)/3] - Cos[2 Pi x/3]) Mod[x, 4] ↔ (3 - 2 Cos[(Pi x)/2] -Cos[Pi x] - 2 Sin[(Pi x)/2])/2 Mod[x, n] ↔ Sum[j Product[(Sin[Pi (x - i - j)/n]/ Sin[Pi i/n])^2, {i, n - 1}], {j, n - 1}]

(As another example, If[x>0, 1, 0] corresponds to 1 - 1/Gamma[1 - x].) And in this way the discrete system x->If[EvenQ[x], 3x/2, 3(x + 1)/2] from page 122 can be emulated by the continuous iterated map x->(3 + 6 x - 3 Cos[Pi x])/4. This approach can then be applied to the universal arithmetic system on page 673, establishing that continuous iterated maps can in principle emulate discrete universal systems. A similar result presumably holds for ordinary and therefore also partial differential equations (PDEs). One might expect, however, that it should be possible to construct a PDE that quite directly emulates a system like a cellular automaton. And to do this approximately is not difficult. For as suggested by the bottom row of pictures on page 732 one can imagine having localized structures whose interactions emulate the rules of the cellular automaton. And one can set things up so that these structures exhibit the analog of attractors, and evolve towards one of a few discrete states. But the problem is that in finite time one cannot expect that they will precisely reach such states. (This is somewhat analogous to the issue of asymptotic particle states in the foundations of quantum field theory.) And this means that the overall state of the system will not be properly prepared for the next step of cellular automaton evolution.

Generating repetitive patterns with continuous systems is straightforward, but generating even nested ones is not. Page 147 showed how Sin[x] + Sin[Sqrt[2] x] has nested features, and these are reflected in the distribution of eigenvalues for ODEs containing such functions. Strange attractors for many continuous systems also show various forms of Cantor sets and nesting.


From Stephen Wolfram: A New Kind of Science [citation]