Constructing Boolean circuits for non-totalistic rules

[apg]

Also, I computed minimal Boolean circuits for all 65536 four-input gates; the output is used by rule2asm.py (in apgmera) to convert outer-totalistic 2D CAs into efficient x86 assembly code.

I wonder what employing a similar method for non-totalistic rules would result in. Possibly there could result some Boolean circuits small enough to adapt for use in apgmera?

An exhaustive search would be infeasible. I was fortunate that I could reduce much of the outer-totalistic rule into computing a 4-input logic gate, and 2^2^4 = 65536 so it was feasible to perform a breadth-first search. On the other hand, the number of 9-input logic gates is 2^2^9 = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096.

Of course, optimality isn't strictly necessary -- it just needs to be reasonably efficient. It's possible to realise any 4-input logic gate (which embodies 16 bits of information) into a circuit of at most 7 logic gates. So, theoretically speaking, each of the 2^102 isotropic rules should be realisable using no more than about 50 logic gates (and maybe run at half the speed of totalistic avxlife).

Now, 102 < 128, so I'm hoping that one can apply some clever sequence of logic gates to summarise the 9 inputs as 7 bits, ensuring that distinct neighbourhoods map to distinct bit-sequences. (Clearly, the centre cell can be one of those 7 bits; we need only compress the 8 neighbours into 6 bits.) Once reduced to a 7-input function, I suspect that a greedy search would result in something reasonable.

Any suggestions?

(The results of this effort would also speed up ntzfind significantly.)

[fluffykitty]

I don't have any ideas, but near-totalistic rules (like B3-e/S23 or B3/S234q) might be simulatable by xoring the nearest totalistic rule with an exception circuit. Is this feasible?

[confocaloid]

What is the status of this problem today? Is it considered 'solved' in some sense?

(Maybe this thread would fit better in Scripts, since it is more about algorithms, rather than about exploring specific CA?)

[...]
Of course, optimality isn't strictly necessary -- it just needs to be reasonably efficient. It's possible to realise any 4-input logic gate (which embodies 16 bits of information) into a circuit of at most 7 logic gates. So, theoretically speaking, each of the 2^102 isotropic rules should be realisable using no more than about 50 logic gates (and maybe run at half the speed of totalistic avxlife).

Now, 102 < 128, so I'm hoping that one can apply some clever sequence of logic gates to summarise the 9 inputs as 7 bits, ensuring that distinct neighbourhoods map to distinct bit-sequences. (Clearly, the centre cell can be one of those 7 bits; we need only compress the 8 neighbours into 6 bits.) Once reduced to a 7-input function, I suspect that a greedy search would result in something reasonable.

Any suggestions?

(The results of this effort would also speed up ntzfind significantly.)

I don't know of a simple or elegant way to compress states of the 8 neighbours into 6 bits.

There is a way to map states of the 8 neighbours into 9 bits. This does not reduce the number of bits, but all rotations and reflections map into the same 9-bit sequence.
For convenience, use Swedish notation, to be able to refer to each of 8 neighbours with a single letter:

Code: Select all

l  n  r
w  -  e
v  s  h

Up to rotations and reflections, there are six possibilities for alive orthogonal neighbours (n, e, s, w):
0, 1, 2 adjacent, 2 opposite, 3, 4.
Current states of orthogonal neighbours can be compressed into three bits, with the following meanings: let the first bit mean "either 2 adjacent or 2 opposite", let second bit mean "either 0 or 4", let third bit mean "0, 1, or 2 opposite".

Similarly, up to rotations and reflections, there are six possibilities for alive diagonal neighbours (l, r, h, v). Current states of diagonal neighbours can be compressed into three more bits.

Three more bits are added, with the following meanings:

• there is at least one run of three or more consecutive alive cells in the neighbourhood (lnrehsvwln)
• there is at least one run of three or more consecutive dead cells in the neighbourhood (lnrehsvwln)
• there are two consecutive alive cells, and there are two consecutive dead cells in the neighbourhood (lnrehsvwl)

I think the resulting 9-bit sequence can be used to distinguish all 51 possibilities, while not distinguishing between rotations/reflections.
Adding one bit for the current state of the middle cell, each of the 102 isotropic 3x3 conditions can be converted into 10 bits.

I wonder if this could be improved (without making the conversion too complicated).

[confocaloid]

[...]
There is a way to map states of the 8 neighbours into 9 bits. This does not reduce the number of bits, but all rotations and reflections map into the same 9-bit sequence.
For convenience, use Swedish notation, to be able to refer to each of 8 neighbours with a single letter:

Code: Select all

l  n  r
w  -  e
v  s  h

[...]
I wonder if this could be improved (without making the conversion too complicated).

Below are listed expressions for the 9 output bits (out0 through out8), in terms of states of the 8 neighbours (nrehsvwl). The current state of the middle cell (c) becomes an output bit out9. Note there are repeated subexpressions (e.g. "and", "or", "xor" of pairs of opposite neighbours).

Code: Select all

-- orthogonal neighbours
o0   := not ((n or s) or (e or w))
o1   := ((n xor s) and not (e or w)) or ((e xor w) and not (n or s))
o2a  := (n xor s) and (e xor w)
o2o  := ((n and s) and not (e or w)) or ((e and w) and not (n or s))
o3   := ((n xor s) and (e and w)) or ((e xor w) and (n and s))
o4   := (n and s) and (e and w)
out0 := o2a or o2o
out1 := o0 or o4
out2 := o0 or o1 or o2o

-- diagonal neighbours
d0   := not ((l or h) or (r or v))
d1   := ((l xor h) and not (r or v)) or ((r xor v) and not (l or h))
d2a  := (l xor h) and (r xor v)
d2o  := ((l and h) and not (r or v)) or ((r and v) and not (l or h))
d3   := ((l xor h) and (r and v)) or ((r xor v) and (l and h))
d4   := (l and h) and (r and v)
out3 := d2a or d2o
out4 := d0 or d4
out5 := d0 or d1 or d2o

-- check whether there is at least one run of three or more
-- consecutive alive cells in the neighbourhood (nrehsvwlnr)
out6 := (n and r and e) or (r and e and h) or (e and h and s) or (h and s and v) or
        (s and v and w) or (v and w and l) or (w and l and n) or (l and n and r)

-- check whether there is at least one run of three or more
-- consecutive dead cells in the neighbourhood (nrehsvwlnr)
out7 := not ((n or r or e) and (r or e or h) and (e or h or s) and (h or s or v) and
             (s or v or w) and (v or w or l) and (w or l or n) and (l or n or r))

-- check whether there are two consecutive alive cells, and also
-- two consecutive dead cells, in the neighbourhood (nrehsvwln)
two1 := (n and r) or (r and e) or (e and h) or (h and s) or
        (s and v) or (v and w) or (w and l) or (l and n)
two0 := not ((n or r) and (r or e) and (e or h) and (h or s) and
             (s or v) and (v or w) and (w or l) and (l or n))
out8 := two1 and two0

-- output one bit for the current state of the middle cell
out9 := c

Below are listed values of the 9 output bits (calculated through the above expressions), for each of the 51 possibilities:

Code: Select all

-------------------
nrehsvwl  876543210
-------------------
11010110  000000001  -- 1
11011010  000001000  -- 8
10010100  000001100  -- 12
01010101  000010110  -- 22
10100100  000100001  -- 33
10101010  000110010  -- 50
11110110  001000000  -- 64
11111110  001000010  -- 66
11111010  001001010  -- 74
11111101  001010000  -- 80
11110101  001010001  -- 81
11111111  001010010  -- 82
11010101  001010100  -- 84
11011101  001010101  -- 85
11101010  001100010  -- 98
11101110  001101010  -- 106
01010100  010000110  -- 134
01010000  010001110  -- 142
10010000  010100100  -- 164
01000000  010100110  -- 166
01000100  010101110  -- 174
10101000  010110000  -- 176
10100000  010110001  -- 177
10000000  010110100  -- 180
10001000  010110101  -- 181
00000000  010110110  -- 182
11010100  100000100  -- 260
11010010  100001001  -- 265
11001010  100100000  -- 288
11001100  100101101  -- 301
11111100  101000000  -- 320
11110100  101000001  -- 321
11011100  101000101  -- 325
11110010  101001000  -- 328
11001001  101001101  -- 333
11101100  101101000  -- 360
11100100  101101001  -- 361
11010000  110001100  -- 396
11011000  110001101  -- 397
11000010  110100001  -- 417
11000000  110100100  -- 420
11001000  110100101  -- 421
11000110  110101001  -- 425
11000100  110101100  -- 428
11110001  111000001  -- 449
11010001  111000100  -- 452
11111000  111001000  -- 456
11110000  111001001  -- 457
11000001  111001100  -- 460
11101000  111100000  -- 480
11100000  111100001  -- 481
-------------------

edit: reversed the order of the output bits.

[confocaloid]

[...] Now, 102 < 128, so I'm hoping that one can apply some clever sequence of logic gates to summarise the 9 inputs as 7 bits, ensuring that distinct neighbourhoods map to distinct bit-sequences. (Clearly, the centre cell can be one of those 7 bits; we need only compress the 8 neighbours into 6 bits.) [...]

[...] There is a way to map states of the 8 neighbours into 9 bits. This does not reduce the number of bits, but all rotations and reflections map into the same 9-bit sequence. [...] I wonder if this could be improved (without making the conversion too complicated).

Well, here is an actual compression (states of the 8 neighbours are packed into 7 bits).

Probably this can be reduced (in the number of intermediate variables, in the number of operations, or both).

Code: Select all

//  neighbourhood:
//    l n r
//    w c e
//    v s h

var output_bits: array [0..7] of Boolean;

procedure compress(const c, n, r, e, h, s, v, w, l: Boolean);
var o0, o1, o2a, o2o, o3, o4,
    d0, d1, d2a, d2o, d3, d4,
    o_gt_d, d_gt_o, r180, nodd,
    run12, run13, run14, run02, run03, run04: Boolean;
begin
  // distinguish possibilities for the four orthogonal neighbours
  o0  := not ((n or s) or (e or w));
  o1  := ((n xor s) and not (e or w)) or ((e xor w) and not (n or s));
  o2a := (n xor s) and (e xor w);
  o2o := ((n and s) and not (e or w)) or ((e and w) and not (n or s));
  o3  := ((n xor s) and (e and w)) or ((e xor w) and (n and s));
  o4  := ((n and s) and (e and w));
  // distinguish possibilities for the four diagonal neighbours
  d0  := not ((r or v) or (h or l));
  d1  := ((r xor v) and not (h or l)) or ((h xor l) and not (r or v));
  d2a := (r xor v) and (h xor l);
  d2o := ((r and v) and not (h or l)) or ((h and l) and not (r or v));
  d3  := ((r xor v) and (h and l)) or ((h xor l) and (r and v));
  d4  := ((r and v) and (h and l));
  // order the 6 possibilities as follows:
  //     "0" < "1" < "2a" < "2o" < "3" < "4"
  // and compare orthogonal vs. diagonal
  // ("_gt_" in variable names means "greater than")
  o_gt_d  := ((d0 or o4) or (o3 and not d3) or (d1 and not o1) or (o2o and d2a)) and not (o0 or d4);
  d_gt_o  := ((o0 or d4) or (d3 and not o3) or (o1 and not d1) or (d2o and o2a)) and not (d0 or o4);
  // does a 180-degree rotation change anything?
  r180 := (n xor s) or (e xor w) or (h xor l) or (r xor v);
  // is the total number of alive neighbours odd?
  nodd := (n xor s) xor (e xor w) xor (h xor l) xor (r xor v);
  // find runs of consecutive alive neighbours
  run12 := (n and r) or (r and e) or (e and h) or (h and s) or
           (s and v) or (v and w) or (w and l) or (l and n);
  run13 := (n and r and e) or (r and e and h) or (e and h and s) or (h and s and v) or
           (s and v and w) or (v and w and l) or (w and l and n) or (l and n and r);
  run14 := (n and r and e and h) or (r and e and h and s) or
           (e and h and s and v) or (h and s and v and w) or
           (s and v and w and l) or (v and w and l and n) or
           (w and l and n and r) or (l and n and r and e);
  // find runs of consecutive dead neighbours
  run02 := not ((n or r) and (r or e) and (e or h) and (h or s) and
                (s or v) and (v or w) and (w or l) and (l or n));
  run03 := not ((n or r or e) and (r or e or h) and (e or h or s) and (h or s or v) and
                (s or v or w) and (v or w or l) and (w or l or n) and (l or n or r));
  run04 := not ((n or r or e or h) and (r or e or h or s) and
                (e or h or s or v) and (h or s or v or w) and
                (s or v or w or l) and (v or w or l or n) and
                (w or l or n or r) and (l or n or r or e));
  // a single "magic bit" is returned, instead of two bits (r180, nodd)
  output_bits[0] := (o_gt_d or d_gt_o or r180) and not nodd;
  // the result of the orthogonal-diagonal comparison
  output_bits[1] := o_gt_d;
  output_bits[2] := d_gt_o;
  // the highest number (x) of consecutive alive neighbours,
  // distinguishing only between four cases:
  // "x < 2" "x = 2" "x = 3" "x > 3"
  output_bits[3] := not run13;            // x < 3
  output_bits[4] := run12 and not run14;  // 1 < x < 4
  // the highest number (y) of consecutive dead neighbours,
  // distinguishing only between four cases:
  // "y < 2" "y = 2" "y = 3" "y > 3"
  output_bits[5] := not run03;            // y < 3
  output_bits[6] := run02 and not run04;  // 1 < y < 4
  // output the current state of the middle cell as a separate bit
  output_bits[7] := c;
end;

And here is the output of a program written to check the above:

Code: Select all

test_canon:  rev[0] = 410 rev[1] = 8 rev[2] = 8 rev[4] = 50 rev[8] = 36
neighbours  output bits
cnrehsvwl   76543210
000001111   00000001  = 1
000000000   00001000  = 8
000001001   00001001  = 9
000000010   00001010  = 10
000001010   00001011  = 11
000000001   00001100  = 12
000000101   00001101  = 13
000001110   00010010  = 18
000000111   00010100  = 20
000000011   00011001  = 25
000001011   00011010  = 26
000001101   00011100  = 28
011111111   00100000  = 32
001101111   00100001  = 33
010111111   00100010  = 34
010101111   00100011  = 35
001111111   00100100  = 36
001011111   00100101  = 37
010101010   00101011  = 43
001010101   00101101  = 45
010101011   00110010  = 50
010111011   00110011  = 51
001010111   00110100  = 52
001110111   00110101  = 53
001101011   00111010  = 58
001011011   00111100  = 60
000111110   01000010  = 66
000011111   01000100  = 68
000101010   01001010  = 74
000100010   01001011  = 75
000010101   01001100  = 76
000010001   01001101  = 77
000101110   01010011  = 83
000010111   01010101  = 85
000100011   01011010  = 90
000110110   01011011  = 91
000010011   01011100  = 92
000011011   01011101  = 93
000111111   01100001  = 97
000101111   01100010  = 98
000111101   01100100  = 100
000101001   01101010  = 106
000100101   01101100  = 108
000111011   01110010  = 114
000100111   01110011  = 115
000110111   01110100  = 116
000111001   01110101  = 117
000110011   01111000  = 120
000101101   01111001  = 121
000101011   01111011  = 123
000110101   01111101  = 125
100001111   10000001  = 129
100000000   10001000  = 136
100001001   10001001  = 137
100000010   10001010  = 138
100001010   10001011  = 139
100000001   10001100  = 140
100000101   10001101  = 141
100001110   10010010  = 146
100000111   10010100  = 148
100000011   10011001  = 153
100001011   10011010  = 154
100001101   10011100  = 156
111111111   10100000  = 160
101101111   10100001  = 161
110111111   10100010  = 162
110101111   10100011  = 163
101111111   10100100  = 164
101011111   10100101  = 165
110101010   10101011  = 171
101010101   10101101  = 173
110101011   10110010  = 178
110111011   10110011  = 179
101010111   10110100  = 180
101110111   10110101  = 181
101101011   10111010  = 186
101011011   10111100  = 188
100111110   11000010  = 194
100011111   11000100  = 196
100101010   11001010  = 202
100100010   11001011  = 203
100010101   11001100  = 204
100010001   11001101  = 205
100101110   11010011  = 211
100010111   11010101  = 213
100100011   11011010  = 218
100110110   11011011  = 219
100010011   11011100  = 220
100011011   11011101  = 221
100111111   11100001  = 225
100101111   11100010  = 226
100111101   11100100  = 228
100101001   11101010  = 234
100100101   11101100  = 236
100111011   11110010  = 242
100100111   11110011  = 243
100110111   11110100  = 244
100111001   11110101  = 245
100110011   11111000  = 248
100101101   11111001  = 249
100101011   11111011  = 251
100110101   11111101  = 253
test_compress: 0 errors.

[confocaloid]

This topic is certainly CA-related, and I think it's quite interesting. Further investigation can help to create better software for simulating and exploring CA.
https://cp4space.hatsya.com/category/bo ... imisation/
https://cp4space.hatsya.com/2022/09/25/ ... nd-errata/
https://gitlab.com/apgoucher/optimal5

[...] (Maybe this thread would fit better in Scripts, since it is more about algorithms, rather than about exploring specific CA?) [...]

Shouldn't this be in sandbox????

No it should not be in sandbox.
Everything in the sandbox is quickly flooded by low S/N, mostly aimless activity.
So (at least in its current state) the sandbox is a bad choice of a place to share something that's a specific topic of interest to other people in the community.

The idea of the sandbox was to serve as a place for newcomers, to understand what these forums are about without cluttering the rest of the conwaylife.com forums.