Monday, January 21, 2013

Turing Automata

Self modifying turing machine based automata on a 2D tape


2D turing machines with 4 possible symbols per space were made. Their state tables were stored in the 'tape' that was used to run the programs, thus allowing self modification. Several of these machines were laid out in the same grid representing the 'tape', and allowed to travel anywhere, modifying themselves or others.


The algorithm is simple. A machine is represented by a 16x16 state table. The columns correspond to the symbols, which also have a direction(More on that later):
  • α(0) -- Displayed as Red, moves Up
  • β(1) -- Displayed as Green, moves Down
  • γ(2) -- Displayed as Blue, moves Left
  • δ(3) -- Displayed as White, moves Right
There are 16 states. Since there are 4 symbols we can use 2 spaces in the table (m,n) to represent all states with 4*m + n.
Also since there are 4 symbols we can use each one to represent which direction to move on the 'tape'. We end up with each row in the table as:
State (α) Direction (α) New Symbol (α) New State(m) (α) New State(n) (β) Direction ... (δ) New State(m) (δ) New State(n)

A lookup based on the current state and symbol underneath is then easily performed. For the actual implementation the state tables and the grid were seeded with random numbers.

Source Code



Timelapsed Videos


As simple as these seem I actually find them pretty interesting. I've not seen them described anywhere else, and they have the property of imposing order on randomness. They always seem to end up in a steady state of repeated behavior, usually 'trains' moving around the screen. I've seen a few interesting things happen, such as piston motions, and really close timing ( moving horizontal chains with small breaks, having diagonal chains going through multiple at once).
Also weird is that it almost always (Roughly 90% of the time) tends towards 2 colors at the end. Also, there is always a dominant color, which makes some sense...I guess. I have alot of other stuff I want to try with them, but I first needed to make sure the basic design worked out.

No comments: