?

Log in

No account? Create an account
 
 
01 November 2005 @ 09:46 pm
Wireworld (no, it doesn't star Kevin Costner)  
Wireworld is a game I've stumbled upon recently. Well, "game" in quotes, since there are no players. I'll explain.

It's a type of game called a "cellular automaton", which is a sort of system "played" on a grid: you start with an arrangement of cells in certain states, and repeatedly apply rules that change the states of cells based on the states of their neighboring cells. Conway's Game of Life (not to be confused with Milton Bradley's Game of Life) is probably the best known, and definitely one of the simplest: there are two possible states (all cells are either "live" or "dead"), and live cells may die from having too few live neighbors ("loneliness") or too many ("overcrowding"), while dead cells may come to life if they have enough live neighbors ("reproduction"). It was a popular way of wasting cycles on idle computers in the early days of microcomputers, and it's possible to make all sorts of nifty mutating, repeating, or infinitely growing(!) patterns on it.

Wireworld is slightly more complicated than the Game of Life. There are four states: insulator (the default state), conductor (also called "copper"), electron head, and electron tail. The rules are: a wire becomes an electron head if it is adjacent (orthogonally or diagonally) to one or two electron heads, an electron head becomes an electron tail, and an electron tail becomes a conductor. It gets its name from the fact that you can create a line of conductor cells (a "wire") and set an "electron" (an electron head cell and electron tail cell adjacent to each other) on it, and the electron will travel along the wire in the direction of the head (the next conductor cell becomes the electron head, the old head becomes the tail, and the old tail turns back into a conductor). This in itself isn't that interesting. What is interesting is that it's actually possible to build more complicated "circuits" such as virtual "logic gates" (the technological basis of binary computing) within this simple framework. In fact, it's theoretically possible to build an entire computer within Wireworld.

Most explorations of Wireworld have used a simple square grid. I wonder whether a hex grid with the same rules would be as flexible? It seems like it'd be more difficult, since while a square cell has 8 neighbors, a hex cell only has 6. Other avenues for exploration include 3D versions: cubic (either 26 neighbors or, if triagonals aren't considered adjacent, 20) or based on a close-packing of spheres (12 neighbors).

Time to flex my geekmuscles.
Tags:
 
 
Current Mood: geekygeeky
Current Music: Soul Flower Union - Eejanaika Takkyu No
 
 
 
Alun Clewealun_clewe on November 5th, 2005 12:52 am (UTC)
Well, you can create "glider guns" that shoot out streams of gliders and act as the inputs--the streams of gliders act as bitstreams, a glider being a 1 and a lack of a glider at the appropriate interval being a 0--, you can create patterns that turn the glider streams in different directions, you can patterns that "detect" the gliders without influencing them, and you can create AND, OR, and NOT logic gates, so I'm pretty sure the answer is yes--that pretty much covers all the fundamental components, and I don't see what else you'd need. In fact, I think the whole reason that it was concluded that you could make a universal Turing machine in Life was because it was discovered how these components could be made.

See here for more information. (Among other pages; this was just the best one I could find in a quick search that covered Life logic gates, but I'm sure there are better pages out there.)
gwalla: lon chaneygwalla on November 5th, 2005 02:10 am (UTC)
Ah, that's interesing! I was under the impression that a Life Turing machine would more closely mimic the theoretical operation of a Turing machine, with a "processor" moving along a "tape".

Actually, while Life is Turing-complete, it's not possible to build a Turing-complete computer in Wireworld. While it's possible to build a computer of arbitrary size (above a certain lower bound), the size of the computer (including memory) remains fixed, since empty cells cannot become conductor cells automatically.