My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

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

The Rule 110 cellular automaton (often simply Rule 110) is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos. In this respect it is similar to Game of Life. Rule 110 is known to be Turing complete. This implies that, in principle, any calculation or computer program can be simulated using this automaton.
In an elementary cellular automaton, a one-dimensional pattern of 0's and 1's evolves according to a simple set of rules. Whether a point in the pattern will be 0 or 1 depends in the new generation on its current value, as well of that of its two neighbors. The Rule 110 automaton has the following set of rules:
current pattern 111 110 101 100 011 010 001 000
new state for center cell 0 1 1 0 1 1 1 0

The name "Rule 110" derives from the fact that this rule can be summarized in the binary sequence 01101110; interpreted as a binary number, this corresponds to the decimal value 110.

In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs ("cliques") in a graph, i.e., sets of elements where each pair of elements is connected.
The clique decision problem is NP-complete. It was one of Richard Karp's original 21 problems shown NP-complete in his 1972 paper "Reducibility Among Combinatorial Problems".

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.
BenFRayfield is offline  

  My Math Forum > College Math Forum > Applied Math

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

Copyright © 2019 My Math Forum. All rights reserved.