The Game of Life Challenge

notes about this webpage: This is not my 'personal site,' 'blog,' or online repository. I dont ever use my university web locker, Im just in a hurry.

12:00 AM: I inventoried the work I need to hand in before noon tomorrow. It came out to about a 20 hour queue. No problem, friday noon was 36 hours away.
12:01 AM: The following question bubbled up from the attentional soup of a wandering mind:
In Conways game of life, what is minimum number of logic gates needed to implement a single cell?
3:xx AM: I get the answer 1091 and find it unsatisfactory. (details later)
5:xx AM: I cannot beat 1091
7:xx AM: Im still confident 1091 is way too large, but my simple tests verify it and i cant bring myself to do anything more sophistocated
11:xx AM: I am still working on this...1091
12:00 PM: I have come to the realization that I have just taken 12 hours I couldnt afford to loose and spent them on a thought I could have forgotten had anything other than nothing happened at 12:02 AM

So apparently reddit is full of awesome hardware hackers. fuck yeah. I humbly link you to a solution submitted by klodolph which is an elegant 35 gate solution

Other redditors suggested reusing chunks of hardware by syncrhonizing the circuit and using a clock to dump monotypical data blocks in and out of the same combinational logic blocks. This is clever, but not really what I originally had in mind. To be fair, this sort of technique is bread and butter in real systems. As far as my nonsense 1091 gate solution I made the mistake of trusting the algorithms without actually using my brain. UncleOxidant pointed out that boolean algebraic reduction schemes (like k-maps) depend heavily on the grouping of terms and ordering of reduction and therefore running my truth table through an algorithm like espresso (which is what i did) gives absolutely no garuntee of optimality.

This proposes a new challenege. The task is the same, minimize the gate count of a combinational GOL cell, but do it by starting from the truth table and designing an algorithm to do the reduction. If i have time later tonight, my plan is build a reduction tree based on recording each grouping/reduction option at each step in the process and then searching the tree for the optimal solution. Ill post the result.

Also for clarification, the circuit need not have a mechanism for executing the "one-step-update", which would mean adding registers at all the inputs and outputs and dumping the output back into the input register that represents the state var. All were building is the purely computation function, F:{0,1}^9->{0,1}^1 Others pointed out that the restriction on using certain gates was arbitrary...indeed. But rather than dig up all sorts arguments about CMOS/TTL logic, gate size in transistors, and other junk, I just dumped the restriction on. One redditor offered up: "just compile some vhdl with no timing and strict area constraints." Now thats just cheating. Also, while I'm sure $oftware$ does a pretty good job circuit optimization, I would doubt that they can achieve true optimality. Also, most of these methods are non-deterministic, using some sort of monte-carlo sampling to try and traverse the solution space. Thanks for playing! impressive solutions and enthusiasm blew my mind

I really need to get my real work done lest I miss a significant and impending deadline. My queue is still 20 hours. There are 24 hours remaining to empty that queue. If I fail, I will be forced to add an additional straw to the back of the burdened camel that is my academic career. I fear for that camel. But im sure many of you programmers recognize the compulsion to continue meaningless programming tasks at the expense of important responsibilities. Some of you may understand the feeling of your brain actively and absolutely restraining you from moving on to other tasks until an acceptable task-termination condition is met. For me there are 2. The first is to prove that the minimal number of gates needed to implemenet a GOL automata is significantly less than 1091...or....
The second option. Find some way to be confident that someone else is working on the same problem. Then you can stop, and check back with them later. Because i need to break out of this loop, this post is me executing that second option.

Hopefully you are familiar with the game of life, if not, then go look it up. You are given 3 primitive logic gates, AND, OR, and NOT. (Yes i am aware that both the NAND and the NOR gates can be composed into all of the others allowing for any circuit to be build from only one primitive). Each GOL cell can be thought of as a function F:{0,1}^9->{0,1}. That is to say, you must build a circuit with 9 inputs and 1 output. Of the 9 inputs, 8 of them represent the 1/0 state of the cell's neighbors in a 2d grid, the other input represents the 1/0 state of the cell itself.
This function could be written down as a truth table, with 2^9 rows and 10 collumns. This table provide an output value for every single permutation of the 9 inputs. More commonly, this function is instead described as a set of nested conditionals. For clarity, the inputs are labelled I0,I1,I2...I7 and S. The output is O. The Game of life is played by computing S[n+1] = F(I0....I7,S[n]).
If S[n]=0:
S[n+1] = 1 if exactly 3 neighbors are 'alive' (state=1)
otherwise S[n+1] = 0

If S[n]=1:
S[n+1] = 1 if exactly 2 neighbors are alive OR if exactly 3 neighbors are alive
otherwise S[n+1] = 0

This is obviously alot easier to write down than a 512 row truth table. There are alot of nice ways to write the update function down so it appears compact and simple. The simplicity of the various expressions of this function is what makes the 1091 minimum-gate implementation so unbelievable. In fact, I think its just plain wrong. To Win, you must find a circuit composed only AND, NOT, and OR that implements the above function. In addition, the sum of the number of ANDS, ORS, and NOTS must be less than 1091. For the curious, 1091 result was found using the algorithm Espresso, which is a logic reduction algorithm. All of my stabs at this problem have started with python code to generate the full 512 row truth table for the function. More python code implements either a karnaugh map reduction or an espresso reduction. Good luck, let me know in the reddit boards how it goes