Skip to content

Latest commit

 

History

History
 
 

turing-complete

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

Cellular Automata and The Game of Life

Turing Completeness

We say a computing system is Turing Complete if it is capable of performing arbitrary, general purpose computation.

Using a construct in The Game of Life called a glider gun, it's possible to build a rudimentary NAND gate in the Game of Life. While a NAND gate by itself isn't enough to be Turing Complete, the "infinite" grid of The Game of Life allows you to use them (or any other functionally complete operator) to build any other type of logical "circuitry" and memory, as well.

Anything computable can be computed in The Game of Life given a large enough grid and enough time. Most people, however, find JavaScript to be a far easier development medium.