GMU:BioArt WS15/Xianzhi Zhang: Difference between revisions

Line 90:

It is possible to construct logic gates such as AND, OR and NOT using gliders. It is possible to build a pattern that acts like a finite state machine connected to two counters. This has the same computational power as a universal Turing machine, so the Game of Life is theoretically as powerful as any computer with unlimited memory and no time constraints: it is Turing complete.

Paul Rendell has implemented a [http://rendell-attic.org/gol/utm/ Universal Turing Machine] in Conway’s Game of Life in 2010. The ~~left~~ picture shows the pattern of it. The ~~right~~ Figure shows the general scheme of this Turing Machine.

Paul Rendell has implemented a [http://rendell-attic.org/gol/utm/ Universal Turing Machine] in Conway’s Game of Life in 2010. The upper picture shows the pattern of it. The lower Figure shows the general scheme of this Turing Machine.

[[File:Game of Life UTM.png|400px|left|thumb|Game of Life UTM snapshot]]

[[File:GoL Turing Machine.png|400px|left|thumb|Diagram of the GoL Turing Machine (Paul Rendell, 2014)]]

The finite state machine part can clearly be seen as the square pattern in the bottom left of the picture. This has an addressing mechanism on the left (state value) and at the bottom (symbol value) and nine memory cells to hold the data table to describe the action for each combination of the internal state and symbol values.

@@ Line 90: / Line 90: @@
 It is possible to construct logic gates such as AND, OR and NOT using gliders. It is possible to build a pattern that acts like a finite state machine connected to two counters. This has the same computational power as a universal Turing machine, so the Game of Life is theoretically as powerful as any computer with unlimited memory and no time constraints: it is Turing complete.
-Paul Rendell has implemented a [http://rendell-attic.org/gol/utm/ Universal Turing Machine] in Conway’s Game of Life in 2010. The left picture shows the pattern of it. The right Figure shows the general scheme of this Turing Machine.
+Paul Rendell has implemented a [http://rendell-attic.org/gol/utm/ Universal Turing Machine] in Conway’s Game of Life in 2010. The upper picture shows the pattern of it. The lower Figure shows the general scheme of this Turing Machine.
 [[File:Game of Life UTM.png|400px|left|thumb|Game of Life UTM snapshot]]
 [[File:GoL Turing Machine.png|400px|left|thumb|Diagram of the GoL Turing Machine (Paul Rendell, 2014)]]
+<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br> <br>
 The finite state machine part can clearly be seen as the square pattern in the bottom left of the picture. This has an addressing mechanism on the left (state value) and at the bottom (symbol value) and nine memory cells to hold the data table to describe the action for each combination of the internal state and symbol values.