David's Blague

This post is a response to the "high level CPU" challenge found here. If you have comments for the public, post them to your own blog. If you have comments for me, send me an email: dbrunton@gmail.com.

It's hard to know where to start with yosefk's post. Perhaps a different post entirely. His definition of "high-level" is as good a place as any. The adjective high-level has meaning in exactly one context. If the behavior of some system differs significantly from the behavior of components of that system, the behavior of the system is high-level, and the behavior of the component is low-level.

The NAND Gate is a great example of this. A NAND Gate by itself is of limited usefulness- it has two inputs and returns 0 if both inputs are 1 otherwise, 1. Not hugely smart. However, it functionally complete. String together enough of them and you've got yourself a CPU. In other posts, I've called such behavior "emergence" though it's a dubious designation in the case of something engineered as much as such a CPU would need to be. Conway's Game of Life, Wolfram's Rule 30 (maybe), NOR gates, C-NOT gates, there are lots of these. Toffoli's CAM-8 was at least one attempt of fabbing automata theory into hardware.

However, yosefk's high-level CPU challenge included these two sentences: "I have images. I must process those images and find stuff in them." None of the machines in the previous paragraph are going to do that better than your current run-of-the-mill silicon wafer. However, yosefk, if you "process" those images by using your eyeballs to look at them, any semantic meaning you derive from them is "high-level". It cannot be predicted by the behavior of any pixel on the image or any one of the receptors on your retina, yet it's there.

Humanity's failure to replicate this kind of behavior in silicon does not in any way invalidate the architecture, and it may in fact be due in part to the bargain you're striking. Millimeters of Silicon? Hell, maybe you shouldn't even be using silicon!

I digress.

Let us go back to the problem of designing high-level hardware. Presumably, one of the reasons I would undergo such an exercise is for the pure joy of it. But I also think there could be some benefit to the architecture- for instance, high-level hardware might excel at solving problems for which low-level hardware is ill-suited. Or high level hardware might become easier for humans to interact with. Perhaps, high-level hardware will do things we haven't thought of yet (this last said with the understanding that if we haven't thought of them they may not be useful). Perhaps, high level hardware will be much like us- good at some tasks, bad at others, but profoundly interesting in both cases.

I digress again.

Here is the outline of my proposal:

1. High-level hardware is made from identical low-level components.
2. Low-level components:
• communicate with up to eight physically proximate neighbors.
  
• implement a truth table of up to eight bits.
• have a small, fixed memory, set at run time (ROM).
• can remember state over a fixed duration of cycles (RAM).
  
• can compare RAM and ROM bitwise for equality.
• can signal halt.
  
3. High-level language defines :
• the truth table currently in use.
  
• a "topology" for low-level components.
• state for low-level components.
• the halting state for low-level components.
4. An outside actor (e.g. Von Neumann computer) might watch what's going on.
   

Now, reading over this, I guess I've just rewritten a bunch of crap that I've written a lot of times before. It's a cellular automaton, with some cruft around it for deciding if it has done anything useful yet. Since it doesn't seem to have "stuck" in the past few cycles, I'll write some pseudo-code this time, so after I get my demo processor it will have something to do.

truth_table( bits: 3, endian: big, packed: 30)
topology(max cells: 40, neighbors: 2, unique: true)
state(default: 0; singularity: 1)
halting(0b1010000110)
run

This code loosely translated into English-ese:

The truth table takes three bits of input. Arrange all combinations of bits in decreasing sequence, and unpack the integer 30 from the big end to tell you the bit-truth value for each three-bit input. Wolfram rule 30.

Each cell acts as an input to two other cells, and receives input from two other cells. The two must be unique in both cases. Hopefully you can kind of see this makes a "ring" of cells. The ring can be a maximum of 40 cells.

The initial state is all zeros, and one 1. In this case, it doesn't matter where the 1 is, but there is only one (it is a singularity, duh).

If the most recent ten bits of state on any given cell are exactly the halting state, that cell signals halt. It notifies the high-level language of completion, and hopefully the high-level language remembers where the completion occurred.

Now, I have described a single instance of such a machine- and I have just riffed the details out of my big shiny brain. Other people have actually built such machines, and they are perfectly capable of performing particular tasks with faster clock time than good-ol x86 and friends.

I certainly haven't gotten it right, but I also firmly agree with all the huffing and puffing by the "C is for Von Neumann Architecture" crowd. Future programming languages are going to run on high-level hardware, they are going to be extraordinarily compact, they are going to perform very specific tasks for which Von Neumann computers are ill suited, and they're probably going to have some Von Neumann architecture watching them closely, since one of the things they'll be bad at is knowing if and when they got the right answer.

I guess they really are like us.

Labels: cellular automata, cpu, response

So, after reading dchud's post about the last applet, I got thinking about various mash-ups I could, well, mash.

I'm still playing around with some variations on clustering and obstacles (something he mentioned in conversation), but realized I needed to make the original a little bit dumber before making it any smarter. Thus, I have replaced the previous applet's behavior of moving cells that are over the threshold to a random location. Now, instead, they move Brownian style. Any cell over its threshold simply swaps with a random pick of the eight cells adjacent to it.

Interestingly, it results in a whole new class of pictures.

Actually, I adjusted the ratio of green/magenta cells to be exactly equal, and removed the "empty" cells, since theres no need of them in the Brownian motion context.

The results are here.

The applet works the same as the other- click to randomize, space to start. It takes a lot longer to settle into a fully stable state, but there are obvious structures only a few generations in. I think it looks kind of like an ant farm.

Labels: brownian motion, cellular automata, pretty, processing, programming, schelling

I've been getting asked a lot (at least twice) about why this site isn't updated more frequently. There are three reasons, really. The first is that I've been doing a lot of writing with a pencil, on paper. I know, shocking. The second is that I've been doing some work on physical things (e.g. soldering iron, circuits, and wood. Yes, the kind of wood that's made from trees). And the last is that it took me a while to figure out how to put Processing Applets on the site. I know, I'm supposed to be good with computers.

The applet I'm about to show you is inspired by a paper written in 1971 by Thomas Schelling, called Dynamic Models of Segregation. It turns out that Schelling's model is a great example of sociology (in which I have a degree) and cellular automata (about which I have an obsession) working together. I'm hardly the first person to notice this.

The basic gist of the program is: there are green cells, magenta cells, and "vacant" cells (white). Each of the green and magenta cells have what I deemed a "socially acceptable" preference for living nearby one another. Specifically, each green cell wants to be in a neighborhood (defined as the cells within three pixels radius) that is at least 1/3 green. Same goes for magenta. If any cell finds this preference violated, it moves to a random empty cell.

The behavior of the system is totally different than the (expected) behavior of an individual. The system segregates quite nicely into green and magenta regions, with a vacant white border in-between. This phenomenon is called emergence. A system displays emergence if its behavior differs from the behavior of its components. Equally as important as the philosophical lesson this applet can teach, is that it makes pretty pictures.

Click the mouse to randomize the picture, and press the space bar to get it going again. It will run on its own the first time through. If you're running Internet Explorer, you may need to click through a few dire warnings to get Java to run.

Without further ado, the Schelling Applet.

Labels: cellular automata, pretty, processing, programming, schelling, sociology