Functioning of Logicell
A- Short reminders about Boole's algebra
B- Automatism and booleans functions
C- Basic principles
D-Construction of Boolean operators (Gates)
E- Construction of an equation
F- Construction of a program
Une ligne juste pour maintenir la largeur de la cellule sous netscape. Une ligne juste pour maintenir la largeur de la cellule sous netscape.
We have seen in Introduction to CA that the Game of Life has Universal computation capabilities. LogiCell shows how the use of guns as generators, gliders as signals and eaters as outputs, can ensure the computation of any Boolean functions.
The applet theoretically permits to test any four input Boolean equation (they may be indefinitely repeated).
A set of combinatory applications shows how to use these functions.
One note concerning speed. The response times
indicated is that of my P400 with IE5.0.
When starting, a working mode must be selected, i.e. :
For the rest, the interface is simple enough to be spontaneously understood.
A- Short reminders about Boole's Algebra1
Booleís algebra, (that is in fact a set of algebra structures) was introduced in 1847 so as to propose an algebraic formulation of logical proposals. This algebraic formulation is made necessary by the ambiguity and complexity of the proposals when expressed through words. Letís consider, for example, the following proposals :
- If at night, all cats are gray and if Garfield is a cat, then Garfield is gray at night.
We recognise a syllogism, form of expression studied since the fifth century before JC as an instrument of codification of a speech and generalised by Aristotle. This proposal is obvious (at least logically)
- If a cat ate the mouse and if Garfield is a cat, the Garfield ate the mouse.
This second proposal is obviously false, but the error doesnít appear spontaneously and itís necessary to reason about it (in this case, Garfield is not the only existing cat Ė and he is all the more the less likely cat to perpetrate such a crime) to become conscious of the error. This example is a trivial one, but imagine a complex set of linked proposals, it then quickly becomes impossible to jump to the validity of the conclusion.
Boole's algebra permits to solve this type of problems.
This algebra works on two values : 1 and 0 (true and false) and uses three operators :
The properties of these operators can be expressed in a truth table
Logical AND (^)
Here, a proposal is true only if both premises are true : " if the weather is fine and if there is snow, Iíll go skiing " if one of these two conditions is not fulfilled, the proposal " Iíll go skiing " is false.
Logical OR (v)
Here, if one of the premises is true, the conclusion will be true too " if my alarm clock doesnít ring or if my car refuses to start, then Iíll be late at work.".
Logical NOT (~]
This operator simply serves to invert the value of a proposal.
Another operator frequently used (notably in LogiCell) is the exclusive OR (Xor) noted w :
In opposition to the classical OR, the conjunct validity of two proposals induced a false conclusion. This operator is not an elementary one, it can be built from the former three ones, for example p w q = (p^~q)v(~p^q). Generally, all operators ( implication, equivalence) can be elaborated from these three elementary operators.
Operators composition laws then ensure Boole's algebra to manage rigorously a complex set of linked proposals.
This algebra is massively used as well in mathematics (demonstration theory, probabilities) as for more practical things (automatism, computingÖ). As far as weíre concerned its interest comes from the fact that the three Boolean operators are theoretically necessary and sufficient to build a Universal Turing Machine2.
To show the practical use of Boolean functions, we chose to present a few automatism applications.
An automatism is a system placed between an operator and a machine. The operator determines the inputs of the automatism in function of the desired result, and the automatism realises a set of operations that determine the values of the outputs sent to the machine. The searches made about automation problems led to the elaboration of a set of mathematical tools (" automatic ") whose use widely overflowed the original field.
Letís take the easy example of a double command. Imagine a stamping press. Itís a machine that (under high pressure) activates a die that will distort a piece of metal to give it a special form. An aspirin tube, for example, is made by the distortion of a piece of metal roughly looking like a coin. To make sure that the hands of the operator are not in the die zone he has to action two switches simultaneously, one for each hand. The electric scheme is an elementary one :
A double command
Both switches must be locked if you want the electricity to each the engine (or, in this case, the relay that will initiate the hydraulic jack). Two conditions must be simultaneously met : this is the Boolean operator AND. If the two switches are plugged in parallel (and not in series as before) youíll get the function OR. One switch closed will be enough to activate the output.
The association of Boolean functions then permits, by a complex treatment of inputs, to build programs - algorithms - reckoning the desired outputs.
The output of a double command exclusively depends on the state of inputs at the "i instant". In fact, the industrial automata also have memory functions. This is named combinatory applications. In fact it is often necessary to determine the output not only in function of the inputs at the "i instant", but also of the state of the inputs at the "i-1 instant". These are sequential applications3. LogiCell doesnít have any memory function, it is then limited to combinatory applications. The following examples will anyway show these ones can also be complex.
LogiCell is a pure Conway. A p30 gun in association with an eater generates the inputs.
The input is on the red cell. If it is on true (or 1), the eater will disappear and let the glider spread. Otherwise the glider is obviously absorbed.
An eater manages the output. The red displayed cell only is activated if an eater absorbs a glider. This cell is the output.
Finally the simple guns (i.e. without eater) are used to build logic operators. Their interest comes from the ability of gliders to destroy each otherís. In LogiCell, the process takes two steps, the first meeting produces two blocks (2x2) then these ones are destroyed by the two following gliders. The introduction of a vertical offset of one cell would have avoided the phase of blocks. The periodicity of the gun allowed me to put the gliders at the same level to simplify the construction of operators.
The only links between the applet and the automata then are :
The automata deals alone with inputs and outputs, it solves the problem on its own.
The three logical operators AND, OR, NO, manage alone the whole Boolean operators (NotAnd or NotOr could have been used too). They are built that way :
And gate with B true and A false
The operator is constructed with two inputs and an opposite direction gun. The output is on the trajectory of the glider of input B. the configurations are :
Gate Or with A and B true
The operator is constructed with two inputs, a same direction gun and an opposite gun. The output is on the trajectory of the glider of input B. The configurations are :
Gate Not with A true
Not A (~A) sends back the opposite of A. The output is on the trajectory of the left gun. The configurations are :
We note that gate A inverts the direction of the output. If an input uses a glider sliding towards the right, the output is on a left glider and vice-versa.
The other logic operators can be built from the three former ones. For example, LogiCell builds the operator Xor as :
A Xor B = (A Or B) And Not(A And B)
An equation is built from the association of several operators. Each operator having two inputs and one output, we use the output of the first operator as an input for the following one. For example :
Equation A And B And C (A^B^C)
The red zone shows a classical AND operator without its output eater. The output of this gate, here Bís glider, is associated to the input C to build the equation (A^B)^C, the output eater is then Cís glider.
This mechanism permits to generate the whole possible combinations, and then the matching equations. The algorithm of LogiCell can manage any number of inputs, the program is limited to four distinct inputs only for simplicity and interface.
Automatism components (algorithms) manage multiple outputs. LogiCell associates various equations on one grid. The program then manages the different outputs according to the problem. We note here the parallel treatment of different equations.
LogiCell proposes some combinatory applications as illustration :
LogiCell is unquestionably technical; its contribution to artificial life is not a direct one. It nevertheless shows an essential part of what we mean when it is said that a Conway automaton, a Life Game, is a Turing machine.
2- Heudin JC, L'évolution au bord du chaos, Hermès, Paris, 1998, p. 122. NAND (Not-And) or NOR (Not-Or) can also generate every Boolean functions.
3- Patrick Trau, IPST, Universitť Louis Pasteur Strasbourg. http://www-ipst.u-strasbg.fr/pat/autom/.
Copyright : This text has been written for an educational purpose. It is free for any private use. If you want to use it for a non-commercial public purpose, please quote author and source. Commercial use is strictly forbidden unless written agreement.
Copyright ©rennard.org. 2000, 2001, 2002.