ConwayLife.com

Forums for Conway's Game of Life
https://conwaylife.com/forums/

A script to write cellular automata as arithmetic expressions

https://conwaylife.com/forums/viewtopic.php?t=6597

Page 1 of 1

A script to write cellular automata as arithmetic expressions

Posted: June 28th, 2024, 1:29 am
by confocaloid
confocaloid wrote: June 24th, 2024, 3:00 am The rules of Conway's Game of Life, written as a single rule that involves only four arithmetic operations:

"If the cell's current state is c and the number of alive neighbours is n, then the cell's state will be f(c,n) in the next generation."

Code: Select all

f(c,n) = (n-8) (n-7) (n-6) (n-5) (n-4) (n-1) n (cn-2n-3c+4) / 1440

Code: Select all

>>> [ [ (n-8)*(n-7)*(n-6)*(n-5)*(n-4)*(n-1)*n*(c*n-2*n-3*c+4) // 1440 for n in range(9) ] for c in range(2) ]
[[0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 1, 0, 0, 0, 0, 0]]
The following Python script accepts a rulestring of a Life-like cellular automaton, and prints an arithmetic expression giving the state of the cell after one tick. The expression can involve c (the current state of the cell; 0 = off, 1 = on) and n (the number of alive neighbours of the cell).
llcapoly.py wrote:

Code: Select all

import sympy
import re

C, N = sympy.symbols(('c', 'n'))

def mk(n):
    numer = sympy.Integer(1)
    denom = 1
    for k in range(9):
        if k != n:
            numer *= (N - k)
            denom *= (n - k)
    return numer / denom

def parse_llca_rulestring(rs):
    m = re.search('^[Bb]([0-8]*)/?[Ss]([0-8]*)$', rs)
    if m is None:
        return None
    b, s = m.groups()
    b = tuple(sorted(set(int(c) for c in b)))
    s = tuple(sorted(set(int(c) for c in s)))
    return (b, s)

def main():
    running = True
    while running:
        print("enter a rulestring (example: B3/S23) or 'exit':")
        rs = input(">>> ")
        if rs.strip().lower() == "exit":
            running = False
        else:
            llca_def = parse_llca_rulestring(rs)
            if llca_def is None:
                print("invalid input.")
            else:
                birth_conditions, survi_conditions = llca_def
                F0 = sum([mk(n) for n in birth_conditions], sympy.Integer(0))
                F1 = sum([mk(n) for n in survi_conditions], sympy.Integer(0))
                F = (1 - C) * F0 + C * F1
                #print('  f0(n) = {}'.format(F0.factor()))
                #print('  f1(n) = {}'.format(F1.factor()))
                print('    f(c, n) = {}'.format(F.expand().factor()))

main()
Example I/O:
python3 llcapoly.py wrote:

Code: Select all

enter a rulestring (example: B3/S23) or 'exit':
>>> B3/S23
    f(c, n) = n*(n - 8)*(n - 7)*(n - 6)*(n - 5)*(n - 4)*(n - 1)*(c*n - 3*c - 2*n + 4)/1440
enter a rulestring (example: B3/S23) or 'exit':
>>> B2/S
    f(c, n) = -n*(c - 1)*(n - 8)*(n - 7)*(n - 6)*(n - 5)*(n - 4)*(n - 3)*(n - 1)/1440
enter a rulestring (example: B3/S23) or 'exit':
>>> B2/S0
    f(c, n) = -(n - 8)*(n - 7)*(n - 6)*(n - 5)*(n - 4)*(n - 3)*(n - 1)*(27*c*n + 2*c - 28*n)/40320
enter a rulestring (example: B3/S23) or 'exit':
>>> B34/S34
    f(c, n) = n*(n - 8)*(n - 7)*(n - 6)*(n - 5)*(n - 2)*(n - 1)*(n + 1)/2880
enter a rulestring (example: B3/S23) or 'exit':
>>> B/S
    f(c, n) = 0
enter a rulestring (example: B3/S23) or 'exit':
>>> B/S012345678
    f(c, n) = c
enter a rulestring (example: B3/S23) or 'exit':
>>> B012345678/S
    f(c, n) = 1 - c
enter a rulestring (example: B3/S23) or 'exit':
>>> exit

Re: write cellular automata as arithmetic expressions

Posted: June 30th, 2024, 7:06 am
by confocaloid
Sometimes, there are two or more "natural" ways to write down a single expression that captures the rules of a cellular automaton.
For example, here is an expression that the script prints for B45/S34:

Code: Select all

f(c, n) = n*(n - 8)*(n - 7)*(n - 6)*(n - 2)*(n - 1)*(8*c*n - 32*c + n**2 - 12*n + 27)/2880
However, since B45/S34 is totalistic (and not just merely outer-totalistic), its rules can be written as a function of (c + n), the total number of alive cells in the neighbourhood:

Code: Select all

g(c, n) = (c + n)*(c + n - 9)*(c + n - 8)*(c + n - 7)*(c + n - 6)*(c + n - 3)*(c + n - 2)*(c + n - 1)/2880
The two functions defined above are different; for example f(2, 9) = 84 while g(2, 9) = 330. Nevertheless, values of the two functions coincide for every valid condition (integer c, n : 0 <= c <= 1, 0 <= n <= 8).

Here is an updated script, renamed to 'otcaexpr.py' due to added support for some outer-totalistic rulespaces beyond Life-like CA:
otcaexpr.py wrote:

Code: Select all

import sympy
import re

class TCA:

    def __init__(self):
        self.__l = None
        self.__C, self.__N = sympy.symbols(('c', 'n'))

    def mk(self, nc):
        numer, denom = sympy.Integer(1), 1
        for k in range(self.get_neighbourhood_size() + 1):
            if k != nc:
                numer *= (self.__N + self.__C - k)
                denom *= (nc - k)
        return numer / denom

    def get_rulestring(self):
        l = ''.join(str(c) for c in self.__l)
        return '{}{}'.format(l, self.get_rulestring_suffix())

    def parse_rulestring(self, rulestring):
        allowed = ''.join(str(c) for c in range(self.get_neighbourhood_size() + 1))
        allowed = '([{}]*)'.format(allowed)
        suffix  = self.get_rulestring_suffix()
        if len(suffix) > 0:
            suffix  = '[{}{}]'.format(suffix.lower(), suffix.upper())
        patt = '^' + allowed + suffix + '$'
        m = re.search(patt, rulestring)
        if m is None:
            self.__l = None
            return False
        l = m.group(1)
        self.__l = tuple(sorted(set(int(c) for c in l)))
        return True

    def get_expression(self):
        F = sum([self.mk(n) for n in self.__l], sympy.Integer(0))
        return F.expand().factor()

class TLLCA(TCA):

    def get_ca_type(self):
        return 'Two-state totalistic CA with range-1 Moore neighbourhood'

    def get_neighbourhood_size(self):
        return 9

    def get_rulestring_suffix(self):
        return ''

class TCAvN(TCA):

    def get_ca_type(self):
        return 'Two-state totalistic CA with range-1 von Neumann neighbourhood'

    def get_neighbourhood_size(self):
        return 5

    def get_rulestring_suffix(self):
        return 'V'

class TCAHex(TCA):

    def get_ca_type(self):
        return 'Two-state totalistic CA with range-1 honeycomb neighbourhood on the hexagonal grid'

    def get_neighbourhood_size(self):
        return 7

    def get_rulestring_suffix(self):
        return 'H'

class OTCA:

    def __init__(self):
        self.__b = None
        self.__s = None
        self.__C, self.__N = sympy.symbols(('c', 'n'))

    def mk(self, n):
        numer, denom = sympy.Integer(1), 1
        for k in range(self.get_neighbourhood_size() + 1):
            if k != n:
                numer *= (self.__N - k)
                denom *= (n - k)
        return numer / denom

    def get_rulestring(self):
        b = ''.join(str(c) for c in self.__b)
        s = ''.join(str(c) for c in self.__s)
        return 'B{}/S{}{}'.format(b, s, self.get_rulestring_suffix())

    def parse_rulestring(self, rulestring):
        allowed = ''.join(str(c) for c in range(self.get_neighbourhood_size() + 1))
        allowed = '([{}]*)'.format(allowed)
        suffix  = self.get_rulestring_suffix()
        if len(suffix) > 0:
            suffix  = '[{}{}]'.format(suffix.lower(), suffix.upper())
        patt = '^[Bb]' + allowed + '/?[Ss]' + allowed + suffix + '$'
        m = re.search(patt, rulestring)
        if m is None:
            self.__b = self.__s = None
            return False
        b, s = m.groups()
        self.__b = tuple(sorted(set(int(c) for c in b)))
        self.__s = tuple(sorted(set(int(c) for c in s)))
        return True

    def get_expression(self):
        F0 = sum([self.mk(n) for n in self.__b], sympy.Integer(0))
        F1 = sum([self.mk(n) for n in self.__s], sympy.Integer(0))
        F = (1 - self.__C) * F0 + self.__C * F1
        return F.expand().factor()

class LLCA(OTCA):

    def get_ca_type(self):
        return 'Life-like CA'

    def get_neighbourhood_size(self):
        return 8

    def get_rulestring_suffix(self):
        return ''

class OTCAvN(OTCA):

    def get_ca_type(self):
        return 'Two-state outer-totalistic CA with range-1 von Neumann neighbourhood'

    def get_neighbourhood_size(self):
        return 4

    def get_rulestring_suffix(self):
        return 'V'

class OTCAHex(OTCA):

    def get_ca_type(self):
        return 'Two-state outer-totalistic CA with range-1 honeycomb neighbourhood on the hexagonal grid'

    def get_neighbourhood_size(self):
        return 6

    def get_rulestring_suffix(self):
        return 'H'

def main():
    ca_types = [ LLCA(), OTCAvN(), OTCAHex(), TLLCA(), TCAvN(), TCAHex() ]
    print("supported CA types:")
    for ca in ca_types:
        print("  {}".format(ca.get_ca_type()))
    running = True
    while running:
        print("enter a rulestring (example: B3/S23) or 'exit':")
        rs = input(">>> ")
        if rs.strip().lower() == "exit":
            running = False
        else:
            for ca in ca_types:
                if ca.parse_rulestring(rs.strip()):
                    print("  CA type   : {}".format(ca.get_ca_type()))
                    print("  rulestring: {}".format(ca.get_rulestring()))
                    print("  f(c, n) = {}".format(ca.get_expression()))
                    break
            else:
                print("invalid input or unsupported rulestring notation.")

main()
An example I/O:
python3 otcaexpr.py wrote:

Code: Select all

supported CA types:
  Life-like CA
  Two-state outer-totalistic CA with range-1 von Neumann neighbourhood
  Two-state outer-totalistic CA with range-1 honeycomb neighbourhood on the hexagonal grid
  Two-state totalistic CA with range-1 Moore neighbourhood
  Two-state totalistic CA with range-1 von Neumann neighbourhood
  Two-state totalistic CA with range-1 honeycomb neighbourhood on the hexagonal grid
enter a rulestring (example: B3/S23) or 'exit':
>>> B3/S23
  CA type   : Life-like CA
  rulestring: B3/S23
  f(c, n) = n*(n - 8)*(n - 7)*(n - 6)*(n - 5)*(n - 4)*(n - 1)*(c*n - 3*c - 2*n + 4)/1440
enter a rulestring (example: B3/S23) or 'exit':
>>> B2/S1
  CA type   : Life-like CA
  rulestring: B2/S1
  f(c, n) = -n*(n - 8)*(n - 7)*(n - 6)*(n - 5)*(n - 4)*(n - 3)*(9*c*n - 11*c - 7*n + 7)/10080
enter a rulestring (example: B3/S23) or 'exit':
>>> B2/S1H
  CA type   : Two-state outer-totalistic CA with range-1 honeycomb neighbourhood on the hexagonal grid
  rulestring: B2/S1H
  f(c, n) = -n*(n - 6)*(n - 5)*(n - 4)*(n - 3)*(7*c*n - 9*c - 5*n + 5)/240
enter a rulestring (example: B3/S23) or 'exit':
>>> B2/S1V
  CA type   : Two-state outer-totalistic CA with range-1 von Neumann neighbourhood
  rulestring: B2/S1V
  f(c, n) = -n*(n - 4)*(n - 3)*(5*c*n - 7*c - 3*n + 3)/12
enter a rulestring (example: B3/S23) or 'exit':
>>> 2
  CA type   : Two-state totalistic CA with range-1 Moore neighbourhood
  rulestring: 2
  f(c, n) = -(c + n)*(c + n - 9)*(c + n - 8)*(c + n - 7)*(c + n - 6)*(c + n - 5)*(c + n - 4)*(c + n - 3)*(c + n - 1)/10080
enter a rulestring (example: B3/S23) or 'exit':
>>> 2H
  CA type   : Two-state totalistic CA with range-1 honeycomb neighbourhood on the hexagonal grid
  rulestring: 2H
  f(c, n) = -(c + n)*(c + n - 7)*(c + n - 6)*(c + n - 5)*(c + n - 4)*(c + n - 3)*(c + n - 1)/240
enter a rulestring (example: B3/S23) or 'exit':
>>> 2V
  CA type   : Two-state totalistic CA with range-1 von Neumann neighbourhood
  rulestring: 2V
  f(c, n) = -(c + n)*(c + n - 5)*(c + n - 4)*(c + n - 3)*(c + n - 1)/12
enter a rulestring (example: B3/S23) or 'exit':
>>> exit

Re: A script to write cellular automata as arithmetic expressions

Posted: September 1st, 2024, 3:01 am
by confocaloid
An updated script, with added support for 2-state outer-totalistic cellular automata with 12-cell neighbourhood on the triangular tiling:
otcaexpr.py wrote:

Code: Select all

import sympy
import re

nbcnt2letter = '0123456789XYZ'

letter2nbcnt = {
    '0': 0,    '1': 1,    '2': 2,    '3': 3,    '4': 4,
    '5': 5,    '6': 6,    '7': 7,    '8': 8,    '9': 9,
    'X': 10,   'x': 10,   'Y': 11,   'y': 11,   'Z': 12,   'z': 12,
    }

def get_allowed_letters(max_neighbours):
    r = set()
    for n in range(max_neighbours + 1):
        r.add(nbcnt2letter[n].lower())
        r.add(nbcnt2letter[n].upper())
    return sorted(r)

class TCA:

    def __init__(self):
        self.__l = None
        self.__C, self.__N = sympy.symbols(('c', 'n'))

    def mk(self, nc):
        numer, denom = sympy.Integer(1), 1
        for k in range(self.get_neighbourhood_size() + 1):
            if k != nc:
                numer *= (self.__N + self.__C - k)
                denom *= (nc - k)
        return numer / denom

    def get_rulestring(self):
        l = ''.join(nbcnt2letter[c] for c in self.__l)
        return '{}{}'.format(l, self.get_rulestring_suffix())

    def parse_rulestring(self, rulestring):
        allowed = ''.join(get_allowed_letters(self.get_neighbourhood_size()))
        allowed = '([{}]*)'.format(allowed)
        suffix  = self.get_rulestring_suffix()
        if len(suffix) > 0:
            suffix  = '[{}{}]'.format(suffix.lower(), suffix.upper())
        patt = '^' + allowed + suffix + '$'
        m = re.search(patt, rulestring)
        if m is None:
            self.__l = None
            return False
        l = m.group(1)
        self.__l = tuple(sorted(set(letter2nbcnt[c] for c in l)))
        return True

    def get_expression(self):
        F = sum([self.mk(n) for n in self.__l], sympy.Integer(0))
        return F.expand().factor()

class TLLCA(TCA):

    def get_ca_type(self):
        return '2-state totalistic cellular automaton with 9-cell Moore neighbourhood'

    def get_neighbourhood_size(self):
        return 9

    def get_rulestring_suffix(self):
        return ''

class TCAvN(TCA):

    def get_ca_type(self):
        return '2-state totalistic cellular automaton with 5-cell von Neumann neighbourhood'

    def get_neighbourhood_size(self):
        return 5

    def get_rulestring_suffix(self):
        return 'V'

class TCAHex(TCA):

    def get_ca_type(self):
        return '2-state totalistic cellular automaton with 7-cell honeycomb neighbourhood on the hexagonal tiling'

    def get_neighbourhood_size(self):
        return 7

    def get_rulestring_suffix(self):
        return 'H'

class OTCA:

    def __init__(self):
        self.__b = None
        self.__s = None
        self.__C, self.__N = sympy.symbols(('c', 'n'))

    def mk(self, n):
        numer, denom = sympy.Integer(1), 1
        for k in range(self.get_neighbourhood_size() + 1):
            if k != n:
                numer *= (self.__N - k)
                denom *= (n - k)
        return numer / denom

    def get_rulestring(self):
        b = ''.join(nbcnt2letter[c] for c in self.__b)
        s = ''.join(nbcnt2letter[c] for c in self.__s)
        return 'B{}/S{}{}'.format(b, s, self.get_rulestring_suffix())

    def parse_rulestring(self, rulestring):
        allowed = ''.join(get_allowed_letters(self.get_neighbourhood_size()))
        allowed = '([{}]*)'.format(allowed)
        suffix  = self.get_rulestring_suffix()
        if len(suffix) > 0:
            suffix  = '[{}{}]'.format(suffix.lower(), suffix.upper())
        patt = '^[Bb]' + allowed + '/?[Ss]' + allowed + suffix + '$'
        m = re.search(patt, rulestring)
        if m is None:
            self.__b = self.__s = None
            return False
        b, s = m.groups()
        self.__b = tuple(sorted(set(letter2nbcnt[c] for c in b)))
        self.__s = tuple(sorted(set(letter2nbcnt[c] for c in s)))
        return True

    def get_expression(self):
        F0 = sum([self.mk(n) for n in self.__b], sympy.Integer(0))
        F1 = sum([self.mk(n) for n in self.__s], sympy.Integer(0))
        F = (1 - self.__C) * F0 + self.__C * F1
        return F.expand().factor()

class LLCA(OTCA):

    def get_ca_type(self):
        return 'Life-like cellular automaton'

    def get_neighbourhood_size(self):
        return 8

    def get_rulestring_suffix(self):
        return ''

class OTCAvN(OTCA):

    def get_ca_type(self):
        return '2-state outer-totalistic cellular automaton with 4-cell von Neumann neighbourhood'

    def get_neighbourhood_size(self):
        return 4

    def get_rulestring_suffix(self):
        return 'V'

class OTCAHex(OTCA):

    def get_ca_type(self):
        return '2-state outer-totalistic cellular automaton with 6-cell honeycomb neighbourhood on the hexagonal tiling'

    def get_neighbourhood_size(self):
        return 6

    def get_rulestring_suffix(self):
        return 'H'

class OTCATri(OTCA):

    def get_ca_type(self):
        return '2-state outer-totalistic cellular automaton with 12-cell neighbourhood on the triangular tiling'

    def get_neighbourhood_size(self):
        return 12

    def get_rulestring_suffix(self):
        return 'L'

def main():
    ca_types = [ LLCA(), OTCAvN(), OTCAHex(), OTCATri(), TLLCA(), TCAvN(), TCAHex(), ]
    print("supported CA types:")
    for ca in ca_types:
        print("  {}".format(ca.get_ca_type()))
    running = True
    while running:
        print("enter a rulestring (example: B3/S23) or 'exit':")
        rs = input(">>> ")
        if rs.strip().lower() == "exit":
            running = False
        else:
            for ca in ca_types:
                if ca.parse_rulestring(rs.strip()):
                    print("  CA type   : {}".format(ca.get_ca_type()))
                    print("  rulestring: {}".format(ca.get_rulestring()))
                    print("  f(c, n) = {}".format(ca.get_expression()))
                    break
            else:
                print("invalid input or unsupported rulestring notation.")

main()
Example I/O:
python3 otcaexpr.py wrote:

Code: Select all

supported CA types:
  Life-like cellular automaton
  2-state outer-totalistic cellular automaton with 4-cell von Neumann neighbourhood
  2-state outer-totalistic cellular automaton with 6-cell honeycomb neighbourhood on the hexagonal tiling
  2-state outer-totalistic cellular automaton with 12-cell neighbourhood on the triangular tiling
  2-state totalistic cellular automaton with 9-cell Moore neighbourhood
  2-state totalistic cellular automaton with 5-cell von Neumann neighbourhood
  2-state totalistic cellular automaton with 7-cell honeycomb neighbourhood on the hexagonal tiling
enter a rulestring (example: B3/S23) or 'exit':
>>> B3/S23
  CA type   : Life-like cellular automaton
  rulestring: B3/S23
  f(c, n) = n*(n - 8)*(n - 7)*(n - 6)*(n - 5)*(n - 4)*(n - 1)*(c*n - 3*c - 2*n + 4)/1440
enter a rulestring (example: B3/S23) or 'exit':
>>> B2/S0
  CA type   : Life-like cellular automaton
  rulestring: B2/S0
  f(c, n) = -(n - 8)*(n - 7)*(n - 6)*(n - 5)*(n - 4)*(n - 3)*(n - 1)*(27*c*n + 2*c - 28*n)/40320
enter a rulestring (example: B3/S23) or 'exit':
>>> B2/S0H
  CA type   : 2-state outer-totalistic cellular automaton with 6-cell honeycomb neighbourhood on the hexagonal tiling
  rulestring: B2/S0H
  f(c, n) = -(n - 6)*(n - 5)*(n - 4)*(n - 3)*(n - 1)*(14*c*n + 2*c - 15*n)/720
enter a rulestring (example: B3/S23) or 'exit':
>>> B2/S0V
  CA type   : 2-state outer-totalistic cellular automaton with 4-cell von Neumann neighbourhood
  rulestring: B2/S0V
  f(c, n) = -(n - 4)*(n - 3)*(n - 1)*(5*c*n + 2*c - 6*n)/24
enter a rulestring (example: B3/S23) or 'exit':
>>> B2/S0L
  CA type   : 2-state outer-totalistic cellular automaton with 12-cell neighbourhood on the triangular tiling
  rulestring: B2/S0L
  f(c, n) = -(n - 12)*(n - 11)*(n - 10)*(n - 9)*(n - 8)*(n - 7)*(n - 6)*(n - 5)*(n - 4)*(n - 3)*(n - 1)*(65*c*n + 2*c - 66*n)/479001600
enter a rulestring (example: B3/S23) or 'exit':
>>> B13579Y/S13579YL
  CA type   : 2-state outer-totalistic cellular automaton with 12-cell neighbourhood on the triangular tiling
  rulestring: B13579Y/S13579YL
  f(c, n) = -n*(n - 12)*(n - 10)*(n - 8)*(n - 6)**2*(n - 4)*(n - 2)*(2*n**4 - 48*n**3 + 368*n**2 - 960*n + 647)/467775
enter a rulestring (example: B3/S23) or 'exit':
>>> B13579Y/S02468XZL
  CA type   : 2-state outer-totalistic cellular automaton with 12-cell neighbourhood on the triangular tiling
  rulestring: B13579Y/S02468XZL
  f(c, n) = (4*c*n**12 - 288*c*n**11 + 9152*c*n**10 - 168960*c*n**9 + 2006862*c*n**8 - 16039584*c*n**7 + 87600656*c*n**6 - 325005120*c*n**5 + 796722784*c*n**4 - 1217027328*c*n**3 + 1028731392*c*n**2 - 357765120*c*n + 467775*c - 2*n**12 + 144*n**11 - 4576*n**10 + 84480*n**9 - 1003431*n**8 + 8019792*n**7 - 43800328*n**6 + 162502560*n**5 - 398361392*n**4 + 608513664*n**3 - 514365696*n**2 + 178882560*n)/467775
enter a rulestring (example: B3/S23) or 'exit':
>>> B45/S348L 
  CA type   : 2-state outer-totalistic cellular automaton with 12-cell neighbourhood on the triangular tiling
  rulestring: B45/S348L
  f(c, n) = n*(n - 12)*(n - 11)*(n - 10)*(n - 9)*(n - 7)*(n - 6)*(n - 2)*(n - 1)*(97*c*n**3 - 1280*c*n**2 + 5171*c*n - 6412*c - 27*n**3 + 360*n**2 - 1341*n + 1512)/43545600
enter a rulestring (example: B3/S23) or 'exit':
>>> B456/S34L
  CA type   : 2-state outer-totalistic cellular automaton with 12-cell neighbourhood on the triangular tiling
  rulestring: B456/S34L
  f(c, n) = -n*(n - 12)*(n - 11)*(n - 10)*(n - 9)*(n - 8)*(n - 7)*(n - 2)*(n - 1)*(32*c*n**3 - 372*c*n**2 + 1540*c*n - 2256*c - 57*n**3 + 702*n**2 - 2895*n + 3906)/43545600
enter a rulestring (example: B3/S23) or 'exit':
>>> exit

Re: A script to write cellular automata as arithmetic expressions

Posted: September 1st, 2024, 12:54 pm
by confocaloid
The same ideas allow writing down a single arithmetic expression that captures all rules of an outer-totalistic cellular automaton with three or more cellstates. However, such expressions become long.

For example, below are listed rules of a "pseudorandom" three-state outer-totalistic cellular automaton with 4-cell von Neumann neighbourhood:

Code: Select all

#RULE (0, 0, 0) => 0
#RULE (0, 0, 1) => 0
#RULE (0, 0, 2) => 2
#RULE (0, 0, 3) => 1
#RULE (0, 0, 4) => 1
#RULE (0, 1, 0) => 1
#RULE (0, 1, 1) => 0
#RULE (0, 1, 2) => 1
#RULE (0, 1, 3) => 0
#RULE (0, 2, 0) => 2
#RULE (0, 2, 1) => 2
#RULE (0, 2, 2) => 2
#RULE (0, 3, 0) => 1
#RULE (0, 3, 1) => 2
#RULE (0, 4, 0) => 1
#RULE (1, 0, 0) => 0
#RULE (1, 0, 1) => 2
#RULE (1, 0, 2) => 2
#RULE (1, 0, 3) => 1
#RULE (1, 0, 4) => 2
#RULE (1, 1, 0) => 0
#RULE (1, 1, 1) => 1
#RULE (1, 1, 2) => 2
#RULE (1, 1, 3) => 2
#RULE (1, 2, 0) => 0
#RULE (1, 2, 1) => 0
#RULE (1, 2, 2) => 0
#RULE (1, 3, 0) => 2
#RULE (1, 3, 1) => 1
#RULE (1, 4, 0) => 2
#RULE (2, 0, 0) => 1
#RULE (2, 0, 1) => 1
#RULE (2, 0, 2) => 0
#RULE (2, 0, 3) => 2
#RULE (2, 0, 4) => 0
#RULE (2, 1, 0) => 2
#RULE (2, 1, 1) => 1
#RULE (2, 1, 2) => 2
#RULE (2, 1, 3) => 2
#RULE (2, 2, 0) => 0
#RULE (2, 2, 1) => 0
#RULE (2, 2, 2) => 2
#RULE (2, 3, 0) => 0
#RULE (2, 3, 1) => 2
#RULE (2, 4, 0) => 2
The rule format used above is "(c, a, b) => r" where c is the current state of the middle cell, a is the number of state-1 neighbours, b is the number of state-2 neighbours, r is the state of the middle cell in the next generation.

And here is a single arithmetic expression that captures all of the above rules:
(109*a**4*b**4*c**2 - 177*a**4*b**4*c + 92*a**4*b**4 - 918*a**4*b**3*c**2 + 1494*a**4*b**3*c - 728*a**4*b**3 + 2327*a**4*b**2*c**2 - 3747*a**4*b**2*c + 1708*a**4*b**2 - 1686*a**4*b*c**2 + 2646*a**4*b*c - 1120*a**4*b + 288*a**4*c**2 - 816*a**4*c + 240*a**4 - 782*a**3*b**4*c**2 + 1262*a**3*b**4*c - 656*a**3*b**4 + 6612*a**3*b**3*c**2 - 10724*a**3*b**3*c + 5120*a**3*b**3 - 16666*a**3*b**2*c**2 + 26746*a**3*b**2*c - 11680*a**3*b**2 + 11556*a**3*b*c**2 - 17908*a**3*b*c + 7120*a**3*b - 1824*a**3*c**2 + 5760*a**3*c - 1824*a**3 + 1511*a**2*b**4*c**2 - 2451*a**2*b**4*c + 1348*a**2*b**4 - 13026*a**2*b**3*c**2 + 21378*a**2*b**3*c - 10312*a**2*b**3 + 32917*a**2*b**2*c**2 - 53529*a**2*b**2*c + 22484*a**2*b**2 - 21234*a**2*b*c**2 + 32658*a**2*b*c - 11744*a**2*b + 2592*a**2*c**2 - 10704*a**2*c + 3792*a**2 - 478*a*b**4*c**2 + 1006*a*b**4*c - 880*a*b**4 + 4980*a*b**3*c**2 - 10372*a*b**3*c + 6688*a*b**3 - 14330*a*b**2*c**2 + 29162*a*b**2*c - 14144*a*b**2 + 9108*a*b*c**2 - 17444*a*b*c + 5552*a*b + 96*a*c**2 + 3456*a*c - 1056*a - 144*b**4*c**2 - 192*b**4*c + 432*b**4 + 576*b**3*c**2 + 2592*b**3*c - 3552*b**3 + 720*b**2*c**2 - 10176*b**2*c + 8784*b**2 - 3456*b*c**2 + 12384*b*c - 5664*b + 576*c**2 - 576*c)/1152
It works for every condition (c, a, b) where 0 <= c <= 2, 0 <= a, 0 <= b, a + b <= 4.

Challenge: Is there a shorter expression that captures all of the above rules?
All times are UTC-04:00
Page 1 of 1

Powered by phpBB® Forum Software © phpBB Limited