# Linear'' chaos via paradoxical set decompositions

tarski.tex

## Abstract

We propose a scenario in which chaotic motion is based on the paradoxical decomposition of attractors by a distance preserving evolution.

## 1  Historical overview

Distance-preserving operations such as translations and rotations can be used to rearrange arbitrary three- (or higher-) dimensional solid objects, which have been paradoxically'' decomposed into finitely many parts, into any other desirable solid object [,]. The term paradoxical'' refers to the facts that

(i)
isometries, i.e., distance-preserving maps, are used;
(ii)
the original object is decomposed into a finite number of parts, and
(iii)
the operation does not preserve the standard (Lebesgue) measures such as volume.

At first sight, the physical applicability of paradoxical decompositions may appear rather remote. Indeed, to our knowledge, only three physical models making use of them have been proposed so far. In one model, Augenstein [,] attempts a description of the strong interaction in terms of the Banach-Tarski paradox. In the second model, Pitowski [,] proposes an explanation for the stronger-than-classical'' (nonlocal'') correlation functions of entangled quantized systems in terms of paradoxical'' measure non-preservation. Very recently, El Naschie has applied the Banach-Tarski theorem in the context of Cantorian Micro Space-time []. Here, we are going to apply these paradoxical set decompositions to dynamical systems, in particular to attractors.

The developement of paradoxical decompositions began with the formalization of measure theory at the beginning of the twentieth century. It was inspired by Cantorian (naive) set theory. Cantor's approach [] encouraged the invention of new types of sets with sometimes bizarre and mindboggling'' features.

We shortly review the classical example due to Vitali 1905. It is a non-Lebesgue measurable set of real numbers. Consider the equivalence relation (for a definition of equivalence relation see below) on real numbers in the interval [0,1): x ~ y iff x - y is a rational number.

If we collect all numbers of [0,1) which are equivalent in the above sense into separate, disjoint sets or classes (these are referred to as equivalence classes), we gain a decomposition of the interval [0,1). The equivalence classes cover the interval. The axiom of choice tells us that we can pick one number from each of these classes and collect them into a set M. This set M Ì [0,1) cannot be measurable: For each rational number r, let Mr = { x +r: x Î M }. By construction of M, two sets Mr, Mr¢ with r ¹ r¢ are mutually disjoint. (To prove this, one could just assume the opposite, arriving at a contradiction.) Note that every real number s in [0,1) belongs to some unique Mr. Let s Î [0,1) be an arbitrary real. Then s must belong to a unique equivalence class under the relation ~ as defined above. Now assume that s¢ is the representant of this class, which was picked out of the class and put into the set M. Now q = s - s¢ is rational, because s, s¢ belong to the same equivalence class. If we write now s¢+ q = s we see clearly that s Î Mq.

Notice further that if M were measurable, each Mr would have the same measure as M, because each element of M is just shifted by a constant. Just like [0,1) has the same measure as [1,2). Let us consider two cases: (i) M is a null set (having measure 0), and (ii) M has nonvanishing, positive measure. If M were a null set, then the intervall [0,1) would be the countable union of null sets, and so-by the definition of Lebesgue measure-should have measure 0, which is incorrect. On the other hand, if M would have some nonvanishing, positive measure-no matter how small (but finite)-then all the Mr would have such a measure too. And the interval

[0,1) = È{Mr:r is rational and 0 £ r £ 1 } must have infinite measure. This again is incorrect.

This whole construction was inspired by the apparent weakness of the Lebesgue measure. Not every set is Lebesgue measurable - and accordingly there are functions which cannot be integrated over certain domains.

Researchers in the field were considering various concepts, attempting to provide a universal measure, which would make every set measurable. But instead of resolving this issue, they discovered even more mindboggling'' objects. Ten years after Vitali's original example, Vitali and Hausdorff constructed a truly surprising paradox on the surface of a sphere (we will come to this later on). Again, this was done to show the nonexistence of a certain measure.

This inspired 20 years of fruitful work. One of the famous results encountered during these investigations was the Banach-Tarski Paradox. In order to properly discuss the Banach-Tarski paradox and to be able to state it precisely, a few terms will be introduced.

## 2  Equidecomposability and paradoxical decompositions

In the following, we shortly introduce the terminology and some necessary techniques. One central idea is the decomposition of sets by equivalence relations.

Recall that an equivalencerelation ~ on a set S is defined to be: (i) symmetric x ~ y ® y ~ x "x,y Î S , (ii) reflexiv x ~ x "x Î S ; and (iii) transitiv x ~ y and y ~ z ® x ~ z "x,y,z Î S. By x ~ y we mean: the relation ~ holds between x and y.

We shall frequently speak of a group G acting on a set X. By this we mean that, to each g Î G, there corresponds a bijection on the set X. Suppose a group G acts on X and A, B Í X. Then A and B are G-equidecomposable or piecewise G-congruent, if A and B can each be partitioned into the same finite number of respectively G-congruent pieces. Formally, A = Èi = 1nAi, B = Èi = 1nBi, Ai ÇAj = Bi ÇBj = Æ if i < j £ n, and there exist g1,¼,gn Î G such that, for each i £ n,gi(Ai) = Bi. We shall sometimes denote the equidecomposability with respect to G by A ~ G B. It is straightforward to prove that this is an equivalence relation.

Let G be a group acting on a set X and suppose E Í X. E is G-paradoxical (or, paradoxical with respect to G) if, for some positive integers m, n, there exist pairwise disjoint subsets A1,¼,Am,B1,¼,Bn of E and g1,¼,gm,h1,¼,hn Î G such that E = Ègi(Ai) and E = Èhj(Bj). So, loosely speaking, a paradoxical set has two disjoint subsets, which can be taken apart and rearranged using G to cover all of the original set.

Alternatively: Let G be a group acting on a set X and suppose E Í X. E is G-paradoxical, if for a positive integer n, there exist pairwise disjoint subsets A1,¼,An of E and g1,¼,gn Î G such that Èi = 1nAi is a proper subset of E, but Èi = 1ngi(Ai) = E.

Using the notion of equidecomposability, one can rephrase the notion of a set being G-paradoxical. E is G-paradoxical if and only if E contains two disjoint subsets A and B such that A ~ G E and B ~ GE. So, if G is a group acting on X and E, E¢ are G-equidecomposable subsets of X, then if E is G-paradoxical, so is E¢.

Finally we shall define an isometry to be a distance preserving bijection on some metric space M. A simple example is the \Bbb R3 and the group of rotations. We shall call a transformation linear if it can be achieved via distance preserving operations.

### 2.1  Nonlinear case

Here we will look at transformations which, while being bijections (they must be bijections in order to be group actions), are not distance preserving. We shall consider metric spaces, of which \Bbb Rn is an example.

#### 2.1.1  Affine maps

Assume that G are the affine maps

 g:x ® t+ax,
where t, a Î \Bbb R, a ¹ 1. Of course, this map is not distance preserving, because d(x,y) = Ö{(x - y)2} ¹ d(g(x),g(y)) = Ö{(t +ax - t -ay)2} for x,y Î \Bbb Rn and

a ¹ 1. Nethertheless, this is a nonchaotic system, because-as we shall see later-the Lyapunov exponent of a system which evolves under such a transformation is 0.

#### 2.1.2  A more general class of nonlinear transformations

Let us now consider transformations of the form

 g:x ® å i Î \Bbb N0 aixbi,
with ai, bi Î \Bbb R, provided that an inverse transformation exists when a special set of bi has been selected. These transformations are in general highly nonlinear. Special cases are e.g. g: x ® x2, g: x ® x3 or the logistic equation xn+1 = f(x) = axn(1-xn) .

In this case, the Lyapunov exponent may be greater than one, and thus deterministic chaos'', i.e., the unfolding of the randomness of the initial value, is possible.

### 2.2  Linear case: the group of distance-preserving transformations

G will now be assumed to be a subgroup of the group of isometries on X. As has been pointed out before, an isometry is a bijection from X to X that preserves distance. Simple examples of isometries are translations and rotations in space.

If G is the whole group of isometries on X, then any subset E Ì X which is G-paradoxical will simply be called paradoxical [[das ist Konvention z.B.: Wagon]]. Using the terminology just introduced, we can formulate the famous Banach-Tarski Paradox as, any ball in \Bbb R3 can be paradoxically decomposed into five pieces and rearranged via isometries such that two and three pieces form an identical copy of the original (ball-doubling').'' Or even more generally, if A and B are two arbitrary bounded subsets of \Bbb R3, each having nonempty interior, then A and B are equidecomposable.''

We shall try to sketch the proof here. As a first step, we shall first discuss Hausdorff's Paradox, which is remarkable in itself.

A sphere S can be decomposed into disjoint sets S = A ÈBÈC ÈQ such that: (i) the sets A,B,C are congruent to each other; (ii) the B ÈC is congruent to each one of the sets A,B,C; and (iii) Q is countable, were we call two sets congruent, if there exists a distance preserving bijection between them.

Let us consider two axes of rotation of the sphere af,ay and consider the group of all rotations generated by rotations f by 180 degrees about af and by rotations y by 120 degrees about ay. All possible rotations under this group consist of repeated applications of the elementary rotations around af or ay. Combined rotations can be described by formal products of such rotations. These products or words' consist of f,y,y2 with the specification that f2 = 1 and y3 = 1, where the symbol 1'' denotes the identity. The axes af,ay can be chosen in such a way that distinct words' describe distinct rotations. For this it suffices to choose the angle q between the axes such that no nontrivial word describes the identity rotation. If it happens to be the identity rotation, then q is the solution of certain equation. This equation has only finitely many solutions. It follows that there are only countably many angles q such that some nontrivial rotation amounts to the identity rotation. Any angle outside this set will do.

We decompose the group G of all words into three disjoint sets A, B, C such that

 Af = B ÈC, Ay = B Ay2 = C.

Now we use the axiom of choice. Each rotation a Î G leaves two points of the sphere fixed. It follows that the set Q of all points on the sphere which are fixed by some rotation a Î G is countable.

Next we consider the set S-Q. This set consists of the points of the sphere which are not fixed by any rotation. We introduce an equivalence relation on this set.

 x ~ y iff y = x a for some a Î G.
So, two points are in the same class if they can be transformed into each other by some rotation. These classes are often called orbits.

By the Axiom of Choice, there exists a set M which contains exactly one element in each orbit. If we let

 A = M A, B = M B, C = M C,

then the sets A,B,C and Q satisfy Hausdorff's theorem. In the above statement M A denotes the set of points which we obtain by applying all the rotations of A to all the points in M. In order to obtain the Banach - Tarski paradox, we first consider the following equivalence relation between sets in the three-dimensional Euclidean space: X ~ Y iff X and Y are equidecomposable. It is easy to verify that this is an equivalence relation and that if X is disjoint from X¢, Y is disjoint from Y¢ and X ~ Y, X¢ ~ Y¢ then XÈX¢ = Y ÈY¢. Using Hausdorff's paradox for the sphere one can use this equivalence relation in a similar way as above to prove Banach Tarski's paradox.

For rather subtle mathematical reasons which we will not discuss here (cf. Wagon's book []), this argument does not hold in one or two dimensions.

This remarkable result amounts to no less then stating that any reasonable object in space can be decomposed into two finite collection of parts, which can then be rearranged via distance-preserving (there is no distorsion, no stretching involved) operations to form two objects, which are equal to the first in any aspect. Stated pointedly: One could, for instance, double and redouble the same cube of gold over and over again. Also, if A is a mosquito and B is an elephant, then one could produce an elephant out of a mosquito. This can be achieved by appropriately cutting'' the mosquito, no matter how small it is, into finitely many pieces and by rearranging those pieces via translations and rotations to become an elephant, no matter how big.

Alas, there is a serious drawback as far as applications are concerned. There is no picture, no intuition of how such isometric miracles could actually be done. The proof of the theorem is essentially nonconstructive, it gives not the slightest hint how such a decomposition must be performed. This is because it appeals to the Axiom of Choice.

One form of the Axiom of Choice is as follows. For every family F of nonempty sets, there exists a function f, often referred to as the choice function, such that f(S) Î S for each set S in the family F. This implies that one can form a set which has exactly one member in common with each of the sets in the family. One needs the Axiom of Choice (AC) in every proof of the existence of a nonmeasurable set. And, of course, the sets to which the Banach Tarski paradox refers to must be nonmeasurable, otherwise there would be a flat contradiction to the additivity of the measure.

These paradoxes use the Axiom of Choice, which is non-constructive. How could one, for instance, choose'' an element of a set of random reals? Surely, in order to be random, any such element must be uncomputably; stronger: algorithmically incompressible []. This nonconstructive feature was often raised as an objection against the use of the Axiom of Choice, especially with respect to physically meaningful'' mathematics. Operationalists like Bridgeman won't allow the use of other then finite, physically possible operations. Also in mathematics this axiom has caused much distress and ongoing discussions. It can be proven that without it there are no nonmeasurable sets. Gödel has proven that the Axiom of Choice is consistent with the rest of set theory. Nethertheless, many models of set theory with weaker axioms have been proposed.

## 3  Dynamical systems

### 3.1  Review of basic notions

Let us now turn to dynamical systems. A differentiable dynamical system is simply a time evolution defined by an evolution equation [dx/ dt] = F(x); in the discrete case, x(n+1) = f(x(n)) where f and F are differentiable functions, acting on elements x of a manifold M. Here, M will usually be \Bbb Rn.

In what follows, we shall briefly review the terms attractor, strange attractor and Lyapunov exponent. Then, we shall discuss the nonlinear and the linear case.

We first give an operational definition of an attractor. An attractor is a set on which experimental points ftx accumulate for large t. Informally speaking, regardless of its initial condition, a system will find itself in a special set of states after some (probably large) time t. This set is called the attractor. Formally, an attractor A can be defined [] as a point set embedded in a manifold M with the following properties:

(i)
all points x Î A are cumulation points of f.
(ii)
If x,y Î A and diam(A) ³ e > 0, then there exist chains of elements x = x0,x1,¼,xn = y and y = y0,y1,¼,ym = x, such that

d(xi,f(g(i))(xi-1)) < e and d(yi,f(g¢(i))(yi-1)) < e with g(i), g¢(i) ³ 1 and 1 £ i £ n.

Here, d is the distance on the manifold M and diam provides a kind of measure for the size' of the attractor A. The last condition just ensures that the attractor cannot be decomposed in smaller attractors which are subsets of A.

An attractor is called strange if, to every d £ diam(A) and e < d, there exists a N(e,d) such that for arbitrary x,y Î A with dist(x,y) < e, dist(fN(x),fN(y)) ³ d. So, informally speaking, in the regime of a strange attractor, two initially arbitrarily close points become arbitrarily separated in time.

The Lyapunov exponent l can be introduced as a measure of the separation of two distinct initial values. If we have an uncertainty interval (x0,x0 + e) at the beginning, after n iterations it becomes (f(n)(x0,f(n)(x0 + e) . The Lyapunov exponent l is defined by

 l(x0) = = lim n ® ¥ 1 n n-1 å i = 0 | log(f¢(x)) |x = xi|.
A system with a positive Lyapunov exponent is sensitive to the initial conditions. Sensitivity to the initial conditions is expressed by calling the system chaotic. Since there is chaotic, unpredictable behaviour but nethertheless each step in the time evolution is well determined by the evolution function one speaks of deterministic chaos.

In what follows, we shall apply the theory of (paradoxical) set decomposition to dynamical systems. We introduce the time evolution operators ft, where t is a real or an integer. Sometimes one requires t ³ 0. The evolution operators have the following properties:
 f0 = identity, fsft = fs+t.
Notice the resemblance to the definition of a generator of a group. Indeed, it is proposed here to identify the time evolution operator with the group action on the manifold M. Remember that a group G is said to act on a set X if, to each g Î G, there corresponds a function (necessarily a bijection) from X to X, which is denoted by g as well, such that for g,h Î G and x Î X, g(h(x)) = (gh)(x) and 1(x) = x, where 1 is the identity of G.

If we now take, for example, \Bbb Rn as the n-dimensional phase space M of a system, the group elements ft propagate the system, whose state is represented by x, through time.

But of course the states of the system which are just points in the phase space can also be viewed as members of a set, namely \Bbb Rn. A subset of the phase space \Bbb Rn is just a set of states of the system.

An attractor too is just a subset of the phase space, and so is a strange attractor. The latter is associated with chaotic behaviour which was characterized above as (eventually) the arbitrarily wide separation of initially arbitrarily close states of the system. We will now look at attractors of nonlinear and linear systems.

### 3.3  Nonlinear case

A system is called Hamiltonian if its equation of motion can be derived from Hamilton's principle. An example is the damped harmonic oscillator. In a Hamiltonian system, the time evolution of the observable is given by [dQ/ dt] = [(Q)/( t)] + {Q,H}. The curly braces { ... } stand for the Poisson brackets.

For a conservative system, that is [(H)/( t)] = 0, Liouville's theorem tells us that the volume in phase space M is conserved by the time evolution. For dissipative systems, this is not the case. The volume in phase space is usually (but not necessarily), contracted. An example is the damped harmonic oscillator: [x\dot] = -y, [y\dot] = x - y. The phase curve tends towards the origin of x-y plane. The origin is the simplest form of an attractor: a fixed point. If we look upon the evolution of a small volume element in phase space, it is clearly not preserved in the evolution of time. Ultimately the dimension of the solutions (of the equations of motion) is reduced from two to zero. Conservation of energy can also expressed by saying that the dimensionality of the solutions stays fixed.

Now we consider another nonlinear system. The Henon attractor arises in a system defined by fx(x,y) = 1 + y - ax2 fy(x,y) = bx. If we take a = 1.4, b = 0.3 we find that

 dx(t) » dx(0)explt, l = 0.42,
i.e. the separation in x grows exponentionally, the Lyapunov exponent is positive, the system is chaotic, the Henon attractor is strange.

If one plots the phase space of this system, one observes that the attractor tends to fill the whole phase space. A set of initial states which is bounded in a narrow region of phase space is expanded by the time evolution function into an evergrowing region.

### 3.4  Linear case

Let us now consider a linear dynamical system. We will call a system linear if the group actions on it are distance preserving, i.e. the dynamical evolution is an isometric bijection. This is a reasonable definition insofar as when one considers two points in phase space (corresponding to two different states of the system), then after some time they will have the same separation in phase space.

Take, as an example, the simple harmonic oscillator. If one plots a diagram of the evolution in phase space, which is just \Bbb R2 for a onedimensional oscillator, one obtains a circle. The points on the circle correspond to the values of the position and the momentum respectively. If one now follows the movements of two points on the circle (these points resemble two different initial conditions, if you like) then one observes that the distance between them stays the same for all times.

So, the simple application of the time evolution function for two different states of the system, e.g. two slightly different initial states, can never separate them arbitrarily wide. The volumes in phase space stay constant. In this view, there seems to be no place for chaotic behaviour to take place.

But now the Banach-Tarski paradox and paradoxical set decompositions come into play. They tell us that by isometric transformations-corresponding to the suggested linear time evolution function-an arbitrary bounded domain in phase space can be doubled and redoubled. Like in nonlinear chaotic systems, sets of initial values bounded to a narrow region of phase space can be expanded to cover an increasingly larger part of the phase space. The attractor of a linear system, which in the case of the harmonic oscillator is just the onedimensional solution of the equation of motion, can be paradoxically decomposed and rearranged. Therefore, the Banach-Tarski paradox in particular, and paradoxical set decompositions by isometries in general, indicate that there may (nonconstructively) exist'' scenarios for linear chaos.

## 4  Summary and discussion

We shortly summarize linear chaos, as it is proposed here. It is characterized by the following features:

(i)
distance-preserving evolution function ft defined on \Bbb Rn, n ³ 3;
(ii)
paradoxical decomposition of the attractor A such that two points x,y Î A become arbitrarily separated by ft.

Stated differently, the hypothesis is this: Supposed the Axiom of Choice holds, then there exists an isometric paradoxical decomposition of any phase space volume in \Bbb Rn, n ³ 3. Therefore, a linear system can show chaotic behaviour.

Note, however, that one may criticise that every constituent of the decomposition gets transfomed differently. Thereby, one may argue, arbitrary separations come as no surprise, since it is always possible to drag'' regions in phase space arbitrarily far apart by translations. Nevertheless, the important feature of the scenario discussed here is an increase of the volume'' of the system in phase space, and not merely separation.

Of course, it is speculative to suggest that such a szenario can actually be realized'' in physics. This brings us to the question of mathematical models for physics [,], in particular the Go-Go'' approch to set theory and physics [].

One may, for instance, oppose nonconstructive methods or methods which cannot be operationalized []. But by the same argument one would be forced to abandon the classical continuum as well. Pick'' an arbitrary element from the classical continuum, and with probability one it is nonconstructive (stronger: algorithmically incompressible; i.e., Martin-Löf/Solovey/Chaitin random [,,])! And even the picking'' operation would be nonconstructive, since it assumes a choice function, which in turn requires the axiom of choice. So, the notion of classical, deterministic chaos is based on nonconstructive methods-the classical continuum and a choice function, by which the system picks'' a Martin-Löf/Solovey/Chaitin random initial value.

Hence, if one abolishes the above scenario because of its nonconstructive features, one faces the grim consequences of having to reinterpret deterministic chaos as well. This could, for instance, be done constructively along a re-interpretation of chaotic motion in physics by undecidability (cf. weak chaos'' [], chapter 13 and []): In such a scenario, the initial value would not be Martin-Löf/Solovey/Chaitin random, but an unknown computable number. Because of the recursive unsolvability of the rule inference problem [,]-a sort of impossibility to guess always correctly the generating law by just watching a generated number sequence-undecidability emerges out of the inability to determine the unknown (but in principle knowable) initial state.

Another way to avoid the above discussed scenario of linear'' chaos, and at the same time not throwing the nonconstructive baby out with the bathwater'' would be to pretend that the classical nonconstructive continuum should be kept but paradoxical set decompositions by isometries do not occur in physics. This approach is not totally convincing, since it introduces an auxiliary hypothesis-the nonexistence of paradoxical set decompositions by isometries. This auxiliary hypothesis becomes even stranger in view of the choice function used in deterministic chaos. For the above reasons, it might be wise not to outrightly oppose linear'' chaos.

## References

[]
S. Banach and A. Tarski, Sur la decomposition des ensembles de points en parties respectivement congruents,'' Fundamenta Mathematicae 6, 244-277 (1924).

[]
St. Wagon, The Banach-Tarski paradox (2nd printing) (Cambridge University Press, Cambridge 1986)

[]
B. W. Augenstein, Hadron physics and transfinite set theory,'' International Journal of Theoretical Physics 23, 1197-1205 (1984).

[]
B. W. Augenstein, Conceiving Nature-Discovering Reality,'' Journal of Scientific Exploration 8, 279-282 (1994).

[]
I. Pitowsky, Phys. Rev. Lett. 48, 1299 (1982); Phys. Rev. Lett. 49, 1216 (1982); Phys. Rev. D27, 2316 (1983).

[]
I. Pitowsky, Quantum Probability - Quantum Logic (Springer, Berlin, 1989).

[]
M. S. El Naschie, Banach-Tarski Theorem and Cantorian Micro Space-time'', in Chaos, Solitons & Fractals 5, 1503 (1995).

[]
G. Cantor, Beiträge zur Begründung der transfiniten Mengenlehre,'' Math. Annalen 46, 481-512 (1895); ibid. 49, 207-246 (1897); reprinted in G. Cantor, Gesammelte Abhandlungen , eds. A. Fraenkel and E. Zermelo (Springer, Berlin, 1932).

[]
G. J. Chaitin, Information, Randomness and Incompleteness, Second edition (World Scientific, Singapore, 1987, 1990); Algorithmic Information Theory (Cambridge University Press, Cambridge, 1987); Information-Theoretic Incompleteness (World Scientific, Singapore, 1992).

[]
C. Calude, Information and Randomness - An Algorithmic Perspective (Springer, Berlin, 1994).

[]
J.-P. Eckmann and D. Ruelle, Rev. Mod. Phys. 57, 617 (1985).

[]
E. Wigner, Remarks on the mind-body question, in The Scientist speculates, ed. by. I. J. Good (Heinemann, London, 1961; Basic Books, New York, 1962); reprinted in J. A. Wheeler and W. H. Zurek, eds.,

Quantum Theory and Measurement (Princeton University Press, Princeton, 1983), pp. 168-181.

[]
R. Landauer, Wanted: a physically possible theory of physics,'' in IEEE Spectrum 4, 105-109 (1967).

[]
K. Svozil, Set Theory and Physics,'' Foundations of Physics, in print.

[]
P. W. Bridgman, A Physicists Second Reaction to Mengenlehre,'' Scripta Mathematica 2, 101-117; 224-234 (1934); cf. also R. Landauer, Advertisement For a Paper I Like,'' in On Limits, ed. by J. L. Casti and J. F. Traub (Santa Fe Institute Report 94-10-056, Santa Fe, NM, 1994), p.39.

[]
K. Svozil, Randomness and Undecidability in Physics (World Scientific, Singapore, 1993).

[]
K. Svozil, A constructivist manifesto for the physical sciences'', in The Foundational Debate, Complexity and Constructivity in Mathematics and Physics, Werner DePauli Schimanovich, Eckehart Köhler and Friedrich Stadler, eds. (Kluwer, Dordrecht, Boston, London, 1995), p. 65-88.

[]
E. M. Gold, Information and Control 10, 447 (1967).

[]
D. Angluin and C. H. Smith, Computing Surveys 15, 237 (1983).

# Contents

1  Historical overview
2.1  Nonlinear case
2.1.1  Affine maps
2.1.2  A more general class of nonlinear transformations
2.2  Linear case: the group of distance-preserving transformations
3  Dynamical systems
3.1  Review of basic notions