4
$\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!

EDIT

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

$\endgroup$

2 Answers 2

5
$\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$
5
  • $\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, 2017 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, 2017 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, 2017 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$ May 27, 2017 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$ May 27, 2017 at 1:36
1
$\begingroup$

I think that your plan is good, but the most important is for it to be intuitive for you ! If you don't feel secure with it, just change it !

Then, for GOL, I made multiple lectures, but as I'm French, I don't think you would like to see them... My habitual plan in order to present it is :

  1. It's a simulation (kind of a game, but a no-player game)
  2. It works with... (an infinite grid, some cells with 2 states, and then some rules)
  3. the rules
  4. beautiful examples (like cambrian explosion in golly)

After that, if you want to speak about the TM from the angle of T-completeness, I suggest you to also just show a bit of $\lambda$-calculus (or at least to speak about Church, for the Church-Turing Thesis), gif you have the time for that.

For your question :

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

If you spoke about $\lambda$-calculus, you will have said that it is equivalent to TM. As you said, logic gates allows to compute any function, including all the possible $\lambda$-functions. You're done.

If you really want to use TM to prove the T-completeness of GOL, you could say that the TM's transition table could simply be a set of logic gates, that takes the actual state etc... and output the new one, that the memory tape could also be a memory made out of logic gates, and finally that the read/write head could be something like a multiplexer and a binary counter, that allows to select a cell and to operate on it, and then to change the cell, to operate again etc...

$\endgroup$
3
  • $\begingroup$ Thank you for your answer! This would have been very helpful at the time, and it will surely be helpful to future readers: take my upvote. Anyway, I edited my question adding a link to the report that I eventually submitted. $\endgroup$
    – Alessandro
    Dec 8, 2020 at 18:13
  • $\begingroup$ Ok, you're Wellcome ! 1) very cool : you use LaTeX ! $\endgroup$ Dec 9, 2020 at 19:47
  • $\begingroup$ 2) I didn't thought it would be a such work: o thought of a lecture, or something like ! So I think that to feel your plan is less important than in a lecture... So my habitual approach of the game of life, while it is made for begginers, could not fit perfectly to a report like your one... $\endgroup$ Dec 9, 2020 at 20:17

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.