3
$\begingroup$

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:

  1. Introduce Turing machines, the notion of universality, and Universal Turing machines.
  2. Introduce the notion of Turing-completeness and its relation with computational universality.
  3. 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:

  1. A form of conditional repetition or conditional jump (while, for, if and goto)
  2. 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:

  1. Is the capability of implementing logical gates (i.e. evaluate any arbitrary logical function) another requirement? Or, is it an alternative requirement?
  2. Which is the correlation between Turing-completeness and logical gates?

Thank you in advance!

$\endgroup$
4
$\begingroup$
  1. A form of conditional repetition or conditional jump (while, for, if and goto)
  2. 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:

latch

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.

$\endgroup$
  • $\begingroup$ I think I understood, but just to be sure: the two requirements I indicated are in fact the necessary conditions for Turing-completenss. It follows that if I'm able to build a machine that satisfies such requirements, then I have a Turing-complete machine. An example of a method (or perhaps the only one?) to build such machine is by using logical gates, as logical gates can be used to implement both conditionals/loops and a storage mechanism. Is everything right? $\endgroup$ – Alessandro May 26 '17 at 16:35
  • $\begingroup$ I've never encountered your particular list for Turing Completelness before, so I can't guarantee it, but it makes intuitive sense that those two criteria would be sufficient, since I am reasonably sure you could simulate a Turing-Complete Instruction with those capabilities. Logic gates are not the only way to prove Turing Completeness. For instance, someone built a full TM in Conway's GoL, but it should be sufficient. You can also talk to your TA if you're unsure. $\endgroup$ – Ben I. May 26 '17 at 16:41
  • $\begingroup$ May I ask which requirements would you point out for Turing-completeness, and how would you prove that functionally-complete logical gates sets (e.g. NANDs) are Turing-complete? It seems I can't find a proper explanation, and I guess I'm somehow searching in the wrong direction. $\endgroup$ – Alessandro May 26 '17 at 17:54
  • $\begingroup$ Your computer is a finite state machine, though it does do an adequate job approximating a Turing machine for most purposes. $\endgroup$ – Derek Elkins May 27 '17 at 1:31
  • 1
    $\begingroup$ More relevantly to your answer, a finite collection of logic gates, even using sequential logic, will only have a finite amount of memory. That you can use flip-flops and latches is irrelevant, you need a mechanism for an unbounded number of them or some other means of unbounded storage. $\endgroup$ – Derek Elkins May 27 '17 at 1:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.