• cellular automata
• discretized wave equation
• meccanica quantistica
• Teorema di Shannon

Cellular Automata (CA) are studied in various fields of science, ranging from physics to the theory of computation, from mathematics to theoretical biology. They present dynamical systems and are used to study, in particular, the evolution of discrete complex systems. They are defined by cells, for example sites on a lattice, which evolve in a synchronized way which is determined in detail by an updating rule. This concept was developed originally by S. Ulam and J. von Neumann at the Los Alamos National Laboratory in the 1940s and only a decade ago it has been proven by M. Cook (and published in "A new kind of Science") that there is a class of CA which are Turing complete. In 1982, in the context of theoretical physics, R.P. Feynman proposed the scheme of a quantum computer (extending the idea of CA) and showed that such a computer is capable of simulating quantum phenomena using quantum mechanics for its operations. A CA is naturally defined on a lattice which introduces a natural unit of length (or time). It has been shown that is possible to define an action that especially leads to a discrete analogue of the Schroedinger equation. The state of a CA can then be viewed as a string of data that contains all relevant information about the corresponding related quantum state.
In information theory, the Shannon Theorem is one of the most important results, which states that the information contained in the denumerable set of all samples of a function on a lattice is equivalent to that contained in a band-limited continuous function; it relates the band-limit to the frequency of sampling. Its use is fundamental for the transmission and evaluation of information, since it allows to convert arrays of data (bits) to analogue signals (such as sound or video).
In Chapter 1 of this thesis, we introduce a general lattice space, an action for a class of CA, and a variational principle by which we recover the evolution rule of the CA, namely the equations of motion. Some particular coupled difference equations of the second order yield the discrete analogue of the Schroedinger equation. A solution is constructed and the continuum limit studied, with the lattice spacing going to zero. We show how it is generally possible to find discrete conservation laws. At the end of this Chapter, we recall relevant aspects from the theory of finite difference equations.
In Chapter 2, we review Shannon’s sampling theorem, in order to map the discrete time Schroedinger equation to a continuous time one, which is modified in an important way: it contains all odd derivatives in time. Thus, there is a natural invertible map between the CA state and the continuous wave function that it represents. We link a stepwise evolution to a continuous time one; this approach allows us to view the results of Chapter 1 from a different perspective and, in particular, we obtain corresponding conservations laws for the continuous representation. We also study mathematical tools which are useful in the study of the scaling of a function: in one case, we modify the length at which we sample, leaving the maximum 1allowed band-limit unchanged; in another case, we use the theory of wavelets to show how it is possible, starting from the sampling of a band-limited function, to construct a scaled
version of it with different band-limits.
In Chapter 3, we focus on the definition of the derivative on the lattice and compare two possibilities. The first one is a local definition (namely the derivative in one point is determined by the difference between the value of the function on the previous and the next point), while the second one is a completely non-local definition, where the derivative depends on the value of the function on all points of the lattice. These two definitions lead to different (quantum mechanical) uncertainty relations. Using the first definition, we obtain a relation of the form ∆x∆p ≥ 1 + β(∆p) 2 - relations of this kind have been discussed in relation possible phenomenological consequences of various approaches to quantum gravity. For the second definition, we obtain ∆x∆p ≥ |1 − n|c n | 2 |, with n defining the size of the lattice and c n a state dependent parameter. This latter result is interesting, since it seems possible to construct states that obey a discrete Schroedinger equation but lead to a “classical” relation of indeterminacy.
In Chapter 4, we present ideas how to extend this discussion also to relativistic equations.
In particular, we use results from Chapter 2 to show how a Lorentz transformation works in this context and what means the passage from one frame of reference to another in terms of CA. We then give the evolution of a state for the discretized Klein-Gordon and Dirac equations.
The final Chapter 5 summarizes our results and shows some further perspective on the presented topics.
In the Appendix, we present some numerical simulations, showing how CA are used to find eigenvalues of a given Hamiltonian; this is has also been found useful for calculations of atomic and molecular bonds.