
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
May 7th, 2013, 05:00 PM  #1  
Senior Member Joined: Jan 2013 Posts: 209 Thanks: 3  2d Clique Crystal is Turing Complete by simulating Rule 110 http://en.wikipedia.org/wiki/Rule_110 Quote:
Quote:
Quote:
Quote:
Now I'll explain very simply why a crystal of cliques can be Turing Complete, capable of general computing. Rule 110 is bandwidth limited to only 3 adjacent bits affecting the bit below its center. Only by applying the rule many time steps can "gliders", as in Conway's Game Of Life, copy patterns through 2 of those 3 bits at a time, between 2 groups of 3 bits each which overlap on 2 bits. There are 8 possible groups of 3 bits. We can view Rule 110 as a 1d cellular automata with 8 colors that can be in each cell. Each cell has a cell up, down, left, right, and the diagonals. Its bandwidth limited to not transfer information faster than that. Like Conway's Game Of Life, a 3x3 grid of cells are the most the center cell can affect each cycle. This is sometimes called the speed of light in Conway's Game Of Life. Rule 110 is simpler. It starts 1d and becomes 2d through time. Conway's Game Of Life is 3d if you include time. So the 3x3 grid is complete in Rule 110. Each of 8 possible colors can be adjacent to only some of the 8 colors in each of those directions (up, down, left, right, and diagonals). Define these as edges in the undirected network. This is how we turn it into a clique math problem. Each cell is 8 nodes which have no edges between eachother because only 1 of them can be true at a time. A cell can only be 1 of 8 colors. We have therefore translated Rule 110 to a clique crystal, a repeating pattern of which of 8 colors can be each of 8 directions from eachother. You could also do it with only 4 directions or expand it to larger than 3x3 to exclude more possibilities at once, but in any case you have to find a clique the size of the number of cells. At any moment of time, Rule 110 has expanded only a finite distance, leaving the "000 becomes 0" color in all cells to the left and right of that area, and the cellular automata version of the "speed of light" proves that color is also outside a triangle expanding downward, its lightcone. Consider that it may be possible to reverse Rule 110 and therefore all possible computing, 1 time step at a time. Or in most cases there are more possible previous steps than 1 that produce a certain state of the 1d row of cells, so it would be necessary to solve the Clique Crystal in 2d. In any case, Clique Crystal of a finite area is in NP, and in an infinite area is Turing Complete. My research path is a little different. I like symmetry, so I'm using spheres which crawl all over eachother. These spheres will have colors and maybe other data that they can read and write in eachother. In the simplest case, a sphere could have a few possible colors, like a superposition of it, and each of those colors would be defined as able to overlap with, and not overlap with, certain colors, an undirected network between all the possible colors. Clique Crystal in this context is the spheres crawling around those they have no edge with and falling into lower energy states when they move into the same space as compatible colors, defined by an edge between the colors in general. Such spheres crawling all over eachother are therefore Turing Complete.  

Tags 
110, clique, complete, crystal, rule, simulating, turing 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Turing complete game 2 AIs can play to measure intelligence  BenFRayfield  Math Events  0  February 20th, 2014 11:39 AM 
Question about simulating finishing order  pearldrumbum  Advanced Statistics  1  September 12th, 2013 09:25 PM 
P equals NP  Max Clique using n dim distance constraints  BenFRayfield  Applied Math  5  May 4th, 2013 11:45 AM 
Help with simulating distributions....  sneaky  Algebra  0  October 30th, 2010 12:29 PM 