Turing-completeness, Conway's Game of Life and Logical Gates

I was recently given an assignment at university asking me to discuss the universal computational capability of Conway's Game of Life.

I'm not required to actually build up a Universal Turing machine in Life, but rather I'm supposed to provide a step-by-step explanation of universality of GoL (as well as the meaning of such result).

I decided to follow this path:

• Introduce Turing machines, the notion of universality, and Universal Turing machines.

• Introduce the notion of Turing-completeness and its relation with computational universality.

• Using such notions and based on previous works and papers, show how Life can be used to simulate a Universal Turing machine.

(Is it a correct reasoning?)

The last point of the assignment asked me to prove the universality of Life by providing an implementation of logical gates in such model, and here come my doubts. I have read dozen of times in StackExchange forums, papers, etc. that the necessary conditions for a system to be Turing-complete are:

• A form of conditional repetition or conditional jump (while, for, if and goto)

• A way to read and write to some storage mechanism

But I never read anywhere about logical gates (or logical propositions in general). So, my questions are:

• Is the capability of implementing logical gates (i.e. evaluate any arbitrary logical function) another requirement? Or, is it an alternative requirement?

• Which is the correlation between Turing-completeness and logical gates?

Thank you in advance!

EDIT

Here is a link to the pdf file of the report that I submitted, thanks for your suggestions!

• A form of conditional repetition or conditional jump (while, for, if and goto)

• A way to read and write to some storage mechanism

The computer you typed this message onto is Turing Complete (well, sort of), yet the only tool it uses is logic gates. I can give you a simple(ish) example of each:

For the first requirement, processors can use multiplexers to create conditional jump options. Multiplexers are basically just a bunch of AND gates.

Number 2 is a bit more complex. Computer memory consists of logic gates that feed back into themselves. If you study memory, you begin by studying latches and flip-flops. Here is a simple latch that stores which of the two input lines on the left turned on most recently:

Thus, it stands to reason that, if you can imitate logical gates, you can create a Turing-Complete machine just as you would if you could simulate a Turing Machine. So, it may be that you don't need to show how to simulate a TM in GoL nodes, but instead take a step to show that logical gates are sufficient to be Turing Complete.

I have one further thought for you that might make your life simpler. You don't need every gate. NAND and NOR are each sufficient, on their own, to create every other logic gate. You can easily do a search like "nand logical completeness" to find the logic gate diagrams to show this.

StackExchange Computer Science Q#75907, answer score: 5