Cellular Automaton Discrete Model

0 0 4 minutes read

A Cellular Automaton is a discrete model similar to any other automaton which has its own start state(s) and a set of rules.

A cellular automaton is a model of a system of “cell” objects with the following characteristics :

The cells live on a grid which can be either 1D or even multi-dimensional

Each cell has a state. The number of state possibilities is typically finite. The simplest example has the two possibilities of 1 and 0

Each cell has a neighbourhood and it is typically a list of adjacent cells

Working principle of Cellular Automata?

The working principle of the cellular automata is shown below:

An initial state is selected by assigning a state for each cell.
A new generation is created, according to some fixed rule that determines the new state of each cell in terms of:
- The current state of the cell.
- The states of the cells in its neighbourhood.
Hence, a new state is calculated by looking at all previous neighbouring states.

Examples of Cellular Automata:

1. Conway’s Game Of Life

2. Rule 90:

Rule 90 is an elementary cellular automaton that consists of a one-dimensional array of cells, each of which can hold either a 0 or a 1 value. Each cell is the exclusive or(XOR) of its two neighbours.

Current State	111	011	101	100	011	010	001	000
Next State	0	1	0	1	1	0	1	0

If we concatenate the Next State into a single binary number and convert it to decimal (01011010)_2, it becomes 90, hence we get the name Rule 90.

3. When the initial state has a single nonzero cell, this diagram has the appearance of the Sierpiński triangle.

Implementation of Sierpiński triangle:

C++

// C++ code to implement Sierpinski Triangle
#include <bits/stdc++.h>
using namespace std;
 
// Length of the string used as a "Seed"
#define LENGTH 34
 
// How many lines the program will generate
int n = 15;
 
// All the patterns possible
vector<vector<int> > rules = { { 0, 0, 0 }, { 0, 0, 1 },
                               { 0, 1, 0 }, { 0, 1, 1 },
                               { 1, 0, 0 }, { 1, 0, 1 },
                               { 1, 1, 0 }, { 1, 1, 1 } };
 
// Utility Function to Print Rules
void printRules()
{
    int i, j;
    cout << "The rules of Rule 90 Cellular Automaton"
            " are as follows: \n";
    for (i = 0; i < 8; i++) {
        cout << "\t\tRule " << i + 1 << ": ";
        for (j = 0; j < 3; j++)
            cout << rules[i][j] << " ";
        cout << "-> sets cell to: "
             << (rules[i][0] 
                 ^ rules[i][2]) << "\n";
    }
}
 
// Print the Current State
void outState(vector<int> s)
{
    cout << "\t\t";
    for (int i = 0; i < LENGTH; i++) {
        if (s[i] == 1)
            cout << "\u25A0";
        else if (s[i] == 0)
            cout << " ";
    }
    cout << "\n";
}
 
// Function to print the triangle
void utilize()
{
    // Initialize starting state 
    // to sierpinski triangle
    vector<int> sierpinski(LENGTH);
    vector<int> updateState(LENGTH);
    sierpinski[(LENGTH) / 2 - 1] = 1;
   
    // Print Sierpinski Triangle
    // initial String
    outState(sierpinski);
 
    // Loop to generate/update the state 
    // and update state arrays
    for (int i = 0; i < n; i++)
    {
        // Erase the old state
        updateState.assign(LENGTH, 0);
       
        // Create the new state
        for (int j = 1; j < LENGTH - 1; j++)
        {
            int f1 = sierpinski[j - 1];
            int f2 = sierpinski[j];
            int f3 = sierpinski[j + 1];
 
            // Create an array with the
            // current pattern
            vector<int> current;
            current.push_back(f1);
            current.push_back(f2);
            current.push_back(f3);
             
            // XOR the current state's neighbours 
            // to set the cell's value 
            // in Update State
            updateState[j] = current[0] ^ current[2];
        }
         
        // Update the current state
        sierpinski.assign(updateState.begin(), 
                          updateState.end());
         
        // Print the new current state
        outState(sierpinski);
    }
}
 
// Driver code
int main()
{
    // Print out the rules for 
    // rule 90 cellular Automaton
    printRules();
    cout << "\n\t\t\tSIERPINSKI TRIANGLE\n\n";
 
    utilize();
    return 0;
}

Output

The rules of Rule 90 Cellular Automata are as follows: 
        Rule 1: 0 0 0 -> sets cell to: 0
        Rule 2: 0 0 1 -> sets cell to: 1
        Rule 3: 0 1 0 -> sets cell to: 0
        Rule 4: 0 1 1 -> sets cell to: 1
        Rule 5: 1 0 0 -> sets cell to: 1
        Rule 6: 1 0 1 -> sets cell to: 0
        Rule 7: 1 1 0 -> sets cell to: 1
        Rule 8: 1 1 1 -> sets cell to: 0

            SIERPINSKI TRIANGLE

                        ■                 
                       ■ ■                
                      ■   ■               
                     ■ ■ ■ ■              
                    ■       ■             
                   ■ ■     ■ ■            
                  ■   ■   ■   ■           
                 ■ ■ ■ ■ ■ ■ ■ ■          
                ■               ■         
               ■ ■             ■ ■        
              ■   ■           ■   ■       
             ■ ■ ■ ■         ■ ■ ■ ■      
            ■       ■       ■       ■     
           ■ ■     ■ ■     ■ ■     ■ ■    
          ■   ■   ■   ■   ■   ■   ■   ■   
         ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!