To see this, consider Conway’s famous Game of Life. You might wonder: are we really asking for more here than just ordinary computational universality? Indeed we are. Then physical universality would mean that we could do that, eventually, by some “machine” we could build outside the 1000×1000 square of interest. So for example, suppose that, given some 1000×1000 square of cells, we’d like to replace every “0” cell within that square by a “1” cell, and vice versa. Suppose we want “physical” universality: that is, the ability to implement any transformation whatsoever on any finite region of the cellular automaton’s state, by suitably initializing the complement of that region. If I’m not mistaken, a guy named Wolfram even wrote an entire 1200-page-long book about this phenomenon ( see here for my 2002 review).īut suppose we want more than mere computational universality. In other words, your cellular automaton becomes able to implement any desired sequence of AND, OR, and NOT gates, store and retrieve bits in a memory, and even (in principle) run Windows or Linux, albeit probably veerrryyy sloowwllyyy, using a complicated contraption of thousands or millions of cells to represent each bit of the desired computation. It’s been understood for decades that, if you take a simple discrete rule-say, a cellular automaton like Conway’s Game of Life-and iterate it over and over, you can very easily get the capacity for universal computation.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |