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 currently0
andBn
is on wheren
is the number ofN1, N2, ..., N8
that are currently set at1
, thenL'
is set to1
. Otherwise, it stays0
.if
L
is currently1
andSn
is off wheren
is the number ofN1, N2, ..., N8
that are currently set at1
, thenL'
is set to0
. Otherwise, it stays1
.
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