문제

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!

올바른 솔루션이 없습니다

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top