http://www.redcientifica.com/gaia/
AUTOMATIC TRANSLATION

http://www.redcientifica.com/gaia/ac/auto_i.htm
English > Artificial Life > Cellular...


Cellular Automatas

Farid Fleifel Tapia - faflta@inf.upv.es
Ricardo Aranguren - ra20914@zurron.upna.es http://www.geocities.com/ResearchTriangle/2262/
Manuel de la Herrán Gascón

Index:


1.- Introduction to the cellular automatas

The studies on automatas finite, machines of Turing, and other models that continue the same philosophy configure it that it is there is designated Theory of Automatas and Machines of Turing, or simply Theory of Automatas, within of the Theory of the Computation.

In the decade of the 50, two neurofisiólogos, Warren S. McCulloch and Walter Pitts designed a model mathematical for to represent the operation of the cells cerebral that it was the origin of the that today it is know for nets neuronales. The model was a approximation very simple to the behavior real of the neurons, but had large applications in other contexts. In the field purely mathematical, Kleene redefined the model and gave place to the automatas finite, kind of machines ideal or models mathematical, to the manner of the machine of Turing, with possibilities quite more reduced, but very adapted for certain processes of calculation.

For other part the english Turing procured to define conceptually a machine of calculation that it is consider universal, it is to say, the mechanism of to process any algorithm. Turing designed a model mathematical of automata that continuing some rules simple was obtaining to solve a great range of problems. In principle, the machine of Turing constitute the instrument of calculation universal, the more general. Not it is possible to give a demonstration rigorous of this, though yes it is has a great quantity of indicia, grouped in it that it is know as Thesis of Church, that puede it be outlined thus: "Not exist functions that they could be defined for persons, and whose calculation it will be described for some algorithm, that not they could it be computed with a machine of Turing". It being based in the machine of Turing, Von Neumann worked in a machine autorreproductiva that called kinematon and in the idea of cellular automata.

[ Back to Index ]


2.- Cellular Automatas

The cellular automatas they are nets of automatas simple connected locally. Each automata simple produces a exit to to depart of several income, modifying in the process its state according to a function of transition. For it general, in a cellular automata, the state of a cell in a generation determined depend only and exclusively of the states of the cells neighboring and of its own state in the generation previous.

The cellular automatas they are tools útiles for to model any system in the universe. They can it be considered as a good alternative to the equations differential and they have been used for to model systems physical, as interactions between particles, training of galaxies, kinetic of systems molecular and growth of crystals, thus as various systems biological to level cellular, multicelular and populational.

[ Back to Index ]


3.- Examples of Cellular Automatas

These three examples of automatas it is they can to unload of the page download.

[ Back to Index ]


3.1.- The game of the life of Conway

One of the cellular automatas more known it is the that John Horton Conway called the game LIFE (Life G me). The game LIFE it is a cellular automata two-dimensional in cuadrícula with two states for cell. Each cell or cell puede be live or died and in each generation it is apply a algorithm that continues these three rules:

1.- Each cell live with two or three cells neighboring live survive to the following generation.

2.- Each cell live with no, a, or more of three cells live to its around passes to be died.

3.- Each cell died with three cells neighboring live resuscitate in the following generation.

The game LIFE present configurations final stable, periódicas or not. Langton defend that present properties of catalysis (actions of construction arbitrational), of transportation (erasing structures and reconstruyéndolas in other place of the space cellular), structural (as elements static, barriers, etc.), of regulation, defense and even informative, and that for so much these automatas virtual have capacities computacionales sufficient for to fulfil the papers functional that play the macromoléculas in the logic molecular of the life. In definitive, that functionally, the automatas they are comparable to the components basic of the life in our planet.

[ Back to Index ]


3.2.- Cells

The program "cells" it is in essence a curiosity scientific proposal for first time for Peter Donnelly of the University College of Swansea, Gales, and Dominic Welsh, of the university of Oxford. The program it was described in detail for TO. K. Dewdney in its article "Five pieces simple" for Scientific American. In this article it is baptize to the program with the name of "voting", already that according to the author intend to simulate a voting political something particular. Citing textualmente:

"The cabins of a cuadriculado rectangular they are colored of white or black, aleatoriamente. It is suppose that each color reflect the opinion political of a person resident in that cabin. A color would to represent 'democrat' and the other 'republican'.
[...]
TO each sign of clock, it is selecciona to the random one of the voters and its opinion political it is submit to change: it is selecciona to the random one of its eight neighboring and the conviction political of the electing it is transform in the of this neighboring, independently of which it would be its opinion previous.
[...]
To the to make to operate this model, confesadamente simplistic, of the process political, occur things striking and miss. First it is develop large blocks of vote homogeneous. These blocks they are zones geographical where all the world it is of the same opinion political. Subsequently such blocks go migrando in wheel to the cuadriculado and, during certain time fight, as seeking its predominance. Finally, the system bipartidista it is comes down, for to finish all the world voting of equal way".

Furthermore of this interpretation of the execution of the program, there is other more approximated, and much more sugerente for the parties in the life artificial and topics related. We can to arrive to to appreciate behaviors "quasi-biological" if we observe the evolution of the voters as a example of the coexistence-competitiveness of two kinds similar in a same middle with abundance of food, as would be the case of two kinds of bacteria in a fluid rich in nutrientes.

The interpertación it is the following: Each position of the counterfoil represent a cell of a kind determined. In each cycle it is chooses aleatoriamente a of the cells of the counterfoil. That cell dies, letting a space free. That space it is occupied immediately of the following form: It is chooses to a of the eight cells contiguous to that space empty for it be reproduced, and the place let for the cell died it occupy a new cell, daughter of the chosen, and for it so much of its same kind.

TO to depart of this behavior so simple we will be able to observe as the chaos initial, in the that the cells of both kinds it is find mixed, gives step to a form of organization in the that the cells of a same kind form wide groups. that it is displace, it is stretch and it is contract while try of to survive.

If it is let the program operating during a time a of the kinds passes to be dominant, being able to to arrive to to make to disappear to the other kind.

Finally, and as curiosity, we could to think in to accomplish in each cycle the reproduction of the cells of a manner something more unusual...

¿What would occur if to the it be reproduced a cell for to occupy the space empty let for other cell died, i had a daughter of the other kind, and not of the his/her/your/their own? ¿Would follow it being produced the homogeneity, or the chaos initial it is would extend until the infinite? TO to depart of the code source of the program, and accomplishing a small modification it is puede to solve this transcendental doubt.

[ Back to Index ]


3.3.- Ants and Plants

Ants and Plants it is a program that require of a certain justification for it be considered as automata. For this it is distinguirán several types of autómtas in function of its objective. This discussion continues in the section Discretización of the time in the automatas of the document "Automatas as analogies of our Universe"

[ Back to Index ]


3.3.1.- Introduction to the types of automatas

Inspirational in the first automatas (as the game of the life of Conway), in the last years they have emerged multitude of models, for it general implemented in programs software, that attempt or well to solve a determined type of problems, or well to represent it more faithfully some aspect concrete of our universe real or of certain universe imaginary.

In how much to the automatas that try of to solve a problem determined, probably the more numerous they will be the collectors, analyzers lexical, syntactic or semantic, in definitive, translators of some type. These automatas they are capable of to read a sequence of symbols written of agreement to a norm or grammar, generating as exit other sequence adjusted to other grammar different. The entry puede be a text in castilian, a program written in language C or a file of data with a determined structure (for example, certain head-board, body and foot). The exit corresponding would be then the text in dutch, the program of ordering in language Lisp or other file of data with a composition different. Other type of automatas that they are being very used they are the Nets Neuronales Artificial, on all in applications of classification (recognition) and forecast.

Within of the second group of automatas, more guided toward the representation and the simulation that toward the resolution, there is a great subgrupo of automatas that intend nothing less that the simulation of the processes of the life. Between they it is find the program "Ants and Plants".

[ Back to Index ]


3.3.2.- Ants and Plants as automata

In the program "Ants and Plants", each a of the cells of the grid in 2 dimensions it is a automata simple with the following states possible:

- Empty
- Occupied for a ant
- Occupied for a plant
- Occupied for a obstacle

Each cell change of state in function of the state of the cells neighboring. For example, a cell in state "plant" passes to state "empty" if there is a ant next to the plant: the ant it is eat the plant. Other changes of state they are subordinated furthermore to the result of a function pseudoaleatoria uniform, and it is produce, if it is fulfil the other conditions, according to a certain probability. For example, a cell in state "empty" passes to state "ant" only if there is a ant next to the plant and furthermore with a certain probability (alone if the ant "decide" to take that address).

The state of each cell puede be defined for different variable: the ants, thus as the plants, possess a certain quantity of energy. But furthermore, the ants possess a inertia in how much to the address of the movement, that provoke a trend to it be moved in the same address, and a "type", already that there is ants "red", "rises", "orange", "yellow" and "green" that correspond with different probabilities of it be moved, to water, it be fought or it be reproduced.

In this automata, the changes of state they are directed solely for the "ants", of form that the "execution" of a ant provoke a change of state in yes same and in other possible cells of type "plant". This last point carry to the possibility of to envisage the program from other point of sight: as a joint of automatas simple mobile whose state it is define, between other, for its position in the shafts X and AND. It is to say, in time of to see a grid whose cells change of state, we see a joint of ants that it is move for some shafts cartesian. In fact, the automata not it is there is programmed as a joint of cells with different properties, but as several joint (or several automatas superposed): a joint of ants, other of plants and other of obstacles, controlling that anyone of they not exist in the same position that other.

[ Back to Index ]


4.- To download source code

In these pages it is offer:

These programs and its files source they are free of charge and of free distribution. The code source it is available and puede be modified, distributed, or used in other programs with deposit freedom.

Click here for to download source code.

[ Back to Index ]

¡You are guest to hold, criticize and collaborate with your ideas!
Send your commentaries, questions, suggestions, or criticize to E-mail
[ Home Page Castellano | Home Page English ]
Translation