Cellular automata. A brief introduction.For readers not familiar with the concept of cellular automata a brief introduction into the subject is given. Readers who are familiar with the concept though, can easily skip this chapter.Although cellular automata nowadays cover a vast area, they all have some features in common. First of all a cellular automaton is a discrete dynamic model that has a spatial and a temporal part. The spatial part is formed by the cells of the automata. It is dynamic in the sense that the spatial appearance of the automaton changes in discrete time steps. This is the temporal part. Cells in the automaton are dependent entities. I.e. they are connected together and therefore each cell has surrounding cells called the neighborhood of the cell. If the cellular automaton would be a two dimensional square lattice, like in a notebook with squared paper, each cell would have 8 neighboring cells. Such a neighborhood is commonly known in cellular automata theory as a Moore neighborhood. Another commonly known neighborhood is the von Neumann neighborhood that comprises the four cells orthogonally surrounding the cells. Both neighborhoods are drawn in the picture below.  It is possible to construct other configurations with the number of direct neighborhood cells ranging from 0 to infinity. A cell with zero direct neighbors would be a singularity. A cell with one direct neighbor would comprise a cellular automaton consisting out of 2 cells. These concepts will be used in the development of the cellular automata in this book. Another important aspect in the dynamics of cellular automata is that every cell can be assigned a value. Most commonly used are the values 1 and 0. However other values are possible. The value of a particular cell is determined by a set of rules and is generally based on the actual value of the cell itself and the values of its neighboring cells. Usually the direct neighbors of the cell are used to determine this value. However it is possible to take into account the second next neighbors of the cell and so on. This will of course complicate the calculations necessary in determining the value of the cell in the next time step. As an example, consider the simple cellular automaton consisting of 3 cells that can each take the values 0 and 1. If the cell has the value 1 it will be colored gray. If it has the value 0 it will be colored white. This automaton then has 23 = 8 states as depicted below. 
It should be noted that for this particular kind of automaton 256 (= 28) transition rules can be constructed since there are eight possible configuration states for 3 cells and each of these can result in two possible outcomes (0 or 1) for the central cell. I.e. it is possible to order the zero’s and one’s in the column titled “Value of Central Cell in next time step” in 28 ways ranging from 00000000 to 11111111 and every possible order in between without changing the values in the other columns. These 256 transition rules result in 256 different cellular automata. These are commonly known as elementary cellular automata. (Actually, the rule given in the table above is commonly known as rule 150 because 10010110 in base 2 is the number 150 in decimal notation). Imagine a row of cells extending to infinity at both sides like in the picture below:    This emergent behavior makes cellular automata very interesting. It shows that quite simple rules on a local level lead to rather complex behavior on a global scale. Although rather brief, this short introduction will give a firm enough base to understand the other chapters in this book. |
maandag 9 april 2012
A Peculiar Class of Cellular Automata
Introduction
It has been suggested by several authors (like for instance Konrad Zuse in his work "Der rechnender Raum") that the mechanism, underlying physical phenomena is in fact a cellular automaton. In other words the universe can be regarded as one big cellular automaton and the physical phenomena observed are due to the emergent behavior of this cellular automaton. Whether this is true remains to be seen. However, it opens up a plethora of possibilities with the main goal of creating a cellular automaton or a class of cellular automata, exhibiting emergent behavior that best mimics the physical phenomena observed in reality. That in itself is an exciting playground filled with challenges like:· How to develop a cellular automaton emerging and growing out of a single cell (big bang singularity).
· How to mimic the conversion of energy into mass and vice versa. (E = mc2)
· How to mimic the phenomenon of two types of electrical charges.
· How to mimic attractive forces over distance. Etc., etc.
Such challenges inherently lead to quite some metaphysical brainstorming in trying to implement them into the desired cellular automaton.
As such the author of this blog is developing an E-book.
This E-book describes the efforts undertaken by the author to develop such a cellular automaton. It does not have the pretension to be a work of scientific thoroughness in the area. It’s more a description of cheerful playing and experimenting with the concept. Just for the sheer fun of it. It should be emphasized that the development and visualization of cellular automata only became practicable with the introduction of fast, easy programmable computers. Computer technology and cellular automata are strongly intertwined. As such it is inevitable to avoid discussions of computer program build up in order to understand the development of the cellular automaton under investigation. In the book example programs are given entirely written in Python. The reader is encouraged to use these programs as a starting point for his/her own experiments. Needless to say that the author's own experiments are still ongoing. So every now and then the book will be updated with new findings. (Time and opportunity given).
This of course still leaves open the question whether all this playing around will prove that the universe actually is one big cellular automaton. For instance, is there any evidence that space and time are in essence discrete opposed to being treated as continuous in most predominant areas of physics? As a matter of fact there are 2 peculiarities in physics pointing into this direction: Planck length and Planck time. Planck length is comprised from 3 different fundamental physical constants: the speed of light in vacuum, Planck's constant and the gravitational constant:
Planck time then is defined as the amount of time it would take a light beam to cross one Planck length. I.e. approximately 5.3875 x 10-44 seconds. It should be emphasized that at the time of writing of this E-book, the physical significance of the Planck length (if any) is not yet known.
The Planck length is extremely small. For illustrative purposes, the (classic) diameter of a proton is estimated at 1 x 10-15 m therefore the Planck length is about 1 x 1020 smaller. This can be compared as the diameter of a hydrogen atom to the diameter of the sun. This directly leads to the feasibility of developing cellular automata based on such small discrete entities. I.e. within the limits of the available computational systems is it possible to observe emergent behavior requiring such an enormous amount of discrete entities? The answer is that it most likely is not possible. However, the solution might lie in taking large ensembles of entities and consider distribution and collision functions. A bit in the manner of the development of Lattice Boltzmann Methods from Lattice Gas Automata.
However, this is all very speculative. Therefore the final answer to the question whether the universe is one big cellular automaton might at the end of the day lead to another question: is not that a matter of belief?
Abonneren op:
Posts (Atom)