7

1

In Conway's Game of Life, a cell is in a state of either on or off, depending on the on-and-off state of the eight cells surrounding it.

We can simulate this using a logic gate network with some sort of clock signal that updates every cell all at once. Your task in this problem is to build the logic gate network for a single cell that will update the new state of the cell given the state of its neighbours.

This cell is a logic gate network that takes eight neighbour-cell inputs `N1, N2, ..., N8`

, the current on/off state of its own cell `L`

, and 18 "rule" inputs `B0, B1, B2, ..., B8`

and `S0, S1, S2, ..., S8`

, and evaluates a new `L`

value (to an output `L'`

) as follows:

if

`L`

is currently`0`

and`Bn`

is on where`n`

is the number of`N1, N2, ..., N8`

that are currently set at`1`

, then`L'`

is set to`1`

. Otherwise, it stays`0`

.if

`L`

is currently`1`

and`Sn`

is off where`n`

is the number of`N1, N2, ..., N8`

that are currently set at`1`

, then`L'`

is set to`0`

. Otherwise, it stays`1`

.

In the example of Conway's Game of Life, `B3`

, `S3`

, and `S2`

are on, while the rest of them are all off.

Unlike my previous logic gate tasks, for this task you may use any two-input logic gates you want, not just NAND gates. This includes exotic gates such as `if A then B`

, `A or not B`

, or simply `A`

, a gate that takes two inputs and always returns the first one (although I'm not sure why you'd want to use that one, you are allowed to). You are allowed unlimited constants, splits, and ground wires.

The network to use the fewest logic gates to achieve this wins.

1Can we use gates that take more than 2 inputs? – Volatility – 2015-01-24T09:00:34.137

1Can we use a "highest bit in a 4-bit adder" 8-input gate as one of our atomic gates? – John Dvorak – 2015-01-24T10:22:34.977

@Volatility If a gate took more than 2 inputs, it wouldn't be a 2ULP (It would be a 3ULP/etc.). So no. – Joe Z. – 2015-01-24T11:31:18.807

@JanDvorak same as Volatility, you'll have to construct it out of smaller gates. – Joe Z. – 2015-01-24T11:31:56.190

OK, we're limited to two inputs, but what what about gates that have more than one output? Say, a half-adder? – John Dvorak – 2015-01-24T12:40:52.643

Nope, a 2ULP always has two inputs and one output. – Joe Z. – 2015-01-24T17:13:40.033

In effect the question is asking you to make a 2D Game of Life cell using any two-input-one-output logic gates you want. – Joe Z. – 2015-01-24T17:18:00.483