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.
Current Mood: geekygeeky
Current Music: Soul Flower Union - Eejanaika Takkyu No
Alun Clewealun_clewe on November 2nd, 2005 06:13 pm (UTC)
You know, right, that it's theoretically possible to build an entire computer within Conway's Game of Life, too?

So the fact it's theoretically possible to build an entire computer within a cellular automaton more complicated than the Game of Life isn't all that surprising...

(Though I'm not sure it's possible to build such nice, visual displays into a Game of Life computer as in there are in that Wireworld computer. This might be the justification for the sentence near the top of the page: "Although at least one design exists for a tape-based Turing machine implemented in the 'Game of Life', ours is, as far as we know, the first ever computer implemented as a cellular automaton that you might reasonably want to write a program for.")
Alun Clewealun_clewe on November 2nd, 2005 06:15 pm (UTC)
Then again, on PCs the visual display is done by a separate peripheral anyway, rather than showing up on the motherboard itself as is (basically) the case with the Wireworld computer...
gwalla: king crimson fingergwalla on November 2nd, 2005 09:35 pm (UTC)
Well, I know that the Game of Life is equivalent to a universal Turing machine. But I don't know if it's possible to "build" a computer out of low-level components equivalent to real electronic gates in it. That's what interests me.
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.