(..CA in SCARLET..)	Contents	Index	(Common Basis: ..)

Example 2 ("FSSP")

The method suggested here goes back to a time optimal solution invented by A. Waksman in 1966 (compare with [5]). The underlying idea is to bisect the retina generating new generals at the same time again and again, until all cells are generals and know by that fact that they have to fire in the next time step. The bisection is done and controlled by signals at distinct speeds; To gain these signals will actually be the challenge of FSSP.

First of all, the general on, say, the left boundary sends out a main signal, which moves to the opposite side at speed 1 (= one cell per time step) and will be reflected there producing a second general on the right boundary.

Additional signals are to be sent out by the first general such that they will happen to meet the main signal on its way back, entering the first half (the first quarter, the first eighths, ...) of the retina.

If the length of the piece of retina they divide in two is an odd number, this will produce one general in the middle, and in case it is even-numbered, two. (In the first case we call the main signal, which is carrying the information about that, 1G-signal, otherwise 2G-signal.)

The new generals are recursively responsible for their (smaller) domains.

Example 4:

If we watch the evolution in time of a one-dimensional retina consisting of 20 cells, we will see the following: (Each line of fields represents the appearance of the retina in a certain time step. The fields shaded stand for the generals.)

Fig. 4: FSSP with 20 fields (scheme).

Considering the example raises the following questions:

1. How do we generate control signals that have the properties we demand?

2. How do we achieve that main and control signals work together well, knowing that the reflection of a main signal at one general will take less time than at two generals? (Remember that the solution should be optimal concerning time!)

In case the main signal is reflected at two generals, the n-th control signal has to move 1 field, while the main signal will cover 2ⁿ⁺¹-1 fields (1 / (2+1), 1 / (4+3), 1 / (8+7), ...). However the control signal must reach the middle at latest at the same time as the main signal. Considering this will lead us to the method of Waksman:

Every second time step the main signals send out a control signal in the opposite direction, while the generals send out a constant signal. When a control signal arrives at a constant signal, it will shift it one field away from the general, who will refresh the constant signal in the next step. Besides, a constant signal lets every second control signal pass so that it can influence constant signals coming behind.

The answer on the second question is actually given by figure 4. If there will be only one general (thus the main signal will move one field less) it is pretended that the control signal was sent out one step earlier; in other terms, the control signals are sent out one time step earlier by 1G-signals than by 2G-signals.

Example 4 (Resumption):

The next figure shows again the time evolution of the 20 fields retina, but now in a realization with 10 states.

We use different generals "G" or "g" depending on if they should send out 1G- or 2G-signals. Soldiers are represented by the state "", control signals by ">" or "<" respectively, constant signals change their state from "1" (permeable) to "2" (impermeable) and back. The main signals are symbolized by "L" and "R". They ''come in two lines'' in order to make clear, if they are 1G- or 2G-signals. At the same time the second line carrys the information whether or not the distance between two generals was even-numbered. Finally "f" denotes the firing state.

Fig. 5: FSSP with 20 fields in a realization with 10 states.

Now it is time to present the complete SDL program belonging to the solution outlined above. In spite of its size no difficult programming structures are used.
The different states are stored in a string register state. To improve the clarity of the code, the register contents of the three neighbours involved are written in variables, first.

A typical entry of the table provides an assignment to the generic cell for single neighbour configurations (e.g., l=="G"; c=="g"; r=="G";) or for certain sets of configurations (e.g., c=="g"; l=="G";) together. In cases that are not mentioned by the table, the state of the generic cell does not change. This time we do not use the notation with SELF known from ''Life'', which requires a cell expression, but we directly assign the values to the register state.

Dealing with bigger local rule tables like this, special care must be taken about the order of the entries. However, entries with more special neighbour configurations must precede more general ones if they include the special case. Otherwise, the special ones will have no effect because of the IF-THEN-ELSE structure of the table.

 

SIGMA fssp;

DIMENSION 1;

REGISTER STRING state;

NEIGHBOUR center : ( 0);
          left   : (-1);
          right  : ( 1);

VAR STRING c, l, r;

TABLE

   /* Assignment to variables */
   /* (always done for it is the first part of the first condition) */

l=left.state; c=center.state; r=right.state; 

 /* fire */

l=="g"|| l=="G"; c=="g"|| c=="G"; r=="g"|| r=="G";  : state="f"; :

 /* the step before the last one */

l=="g"|| l=="G"; r=="g"|| r=="G"; : state="G"; :

 /* creation of a 1G-signal (conversion of the general) */
 /* by a 2G-signal (2 generals) */

c=="g"; l=="G"|| r=="G"; : state="G"; : /* not 3 generals */
  
  /* by a 1G-signal (1 general) */

l==""; c=="g"; r==""; : state="g"; : 
l==""; c=="g"; r=="L"; : state="G"; :
l=="R"; c=="g"; r==""; : state="G"; :

  /* producing a general in the middle */
  /* the first general always */

c=="1"|| c=="2"; l=="R"|| r=="L"; : state="g"; :

  /* the second general only if there arrives a 2G-signal */

l=="1"|| l=="2"; c=="L"; r==">"; : state="G"; : /* 1G-signal */
l=="<"; c=="R"; r=="1"|| r=="2"; : state="G"; :
l=="1"|| l=="2"; c=="L"; r=="<"; : state="g"; : /* 2G-signal */
l==">"; c=="R"; r=="1"|| r=="2"; : state="g"; :
l=="1"|| l=="2"; c=="L"; r=="g"; : state="g"; : /* length==4 */
l=="g"; c=="R"; r=="1"|| r=="2"; : state="g"; :

  /* otherwise: first general receives the information */

l=="1"|| l=="2"; c=="L"; r=="L"; : state=""; : /* 1G-signal */
l=="R"; c=="R"; r=="1"|| r=="2"; : state=""; :
l=="1"|| l=="2"; c=="L"; r==""; : state="L"; : /* 2G-signal */
l==""; c=="R"; r=="1"|| r=="2"; : state="R"; :
l=="1"|| l=="2"; c=="L"; r=="G"; : state="1"; : /* length==5 */
l=="G"; c=="R"; r=="1"|| r=="2"; : state="1"; :

  /* creation of a general on the boundary */

l=="R"; c==""; isborder(right); : state="g"; :
isborder(left); c==""; r=="L"; : state="g"; :

  /* conversion of the general on the boundary for a 1G-signal */

l=="R"; c=="g"; isborder(right); : state="G"; :
isborder(left); c=="g"; r=="L"; : state="G"; :

  /* controling of 1G- and 2G-signals */
  /* creation, reflection at the boundary */

l=="g"; (c=="2"||c=="L"||c==""); : state="R"; :
(c=="2"||c=="R"||c==""); r=="g"; : state="L"; :

  /* movement */

l=="R"; c==""; : state="R"; :  /* isborder(right)==FALSE ! */
c==""; r=="L"; : state="L"; :

  /* More special: 1G-signals */

l=="G"; c==""; : state="R"; : /* creat.: 1G-signal */
c==""; r=="G"; : state="L"; :
l=="G"; c=="R"; r==""; : state="1"; : /* creat.: 1. const. signal */
l==""; c=="L"; r=="G"; : state="1"; :
l=="1"|| l=="R"; c=="R"; r==""; : state=""; : /* movement 1G */
l==""; c=="L"; r=="1"|| r=="L"; : state=""; :
c==""; r=="R"; : state="<"; : /* creat.: control signal */
l=="L"; c==""; : state=">"; :
l=="<"; c=="R"; r=="R"; : state=""; : /* recogn.: 1G-signals */
l=="L"; c=="L"; r==">"; : state=""; :
l==""; c=="R"|| c=="L"; r==""; : state=c; :

  /* more special: 2G-signals */

l=="g"; c=="R"; r==""; : state="<"; : /* creat.: 1. control signal */
l==""; c=="L"; r=="g"; : state=">"; :
l==">"; c=="R"; r==""; : state="<"; : /* creat.: other control sign. */
l==""; c=="L"; r=="<"; : state=">"; :
l=="<"; c=="R"; r==""; : state=">"; : /* recogn.: 2G signals */
l==""; c=="L"; r==">"; : state="<"; :

  /* control signals */

l=="G"|| l=="g"; c=="<"; : state="1"; : /* creat.: const. signals */
c==">"; r=="G"|| r=="g"; : state="1"; :
l=="1"&&c=="<"|| c==">"&&r=="1"; : state="2"; : /* shifts */
l=="2"&&c=="<"|| c==">"&&r=="2"; : state="1"; :
c=="1"; r=="<"; : state="<"; : /* passes 1-signals */
l==">"; c=="1"; : state=">"; :
c=="2"; r=="<"; : state=""; : /* stopped by 2-signals */
l==">"; c=="2"; : state=""; :
c=="2"; l==">"|| r=="<"; : state=""; :
l==">"; c==""; : state=">"; : /* movement */
c==""; r=="<"; : state="<"; :
c==">"|| c=="<"; : state=""; : /* does not meet 1,2,g,G */

Example 4 (Resumption):

A RDL program that models a retina with 20 cells and a proper initial configuration (19 soldiers and the general) is simply given by

RETINA fssp;

RANGE [0]..[19];

REGISTER STRING state;

START
      [0].state = "G";
      [1]..[19].state = "";

(..CA in SCARLET..)	Contents	Index	(Common Basis: ..)