First steps toward programmable matter?
Arguably, since the dawn of the solid state era the human race has been experimenting with the development of computronium, or forms of matter optimized for the processing of information. The doped silicon semiconductors that make up the CPU and much of the supporting circuitry of the computer you're using right now are variants of computronium (albeit very primitive when compared with the above link). Most circuitry as we know it today has a few limitations that we don't often think about, however. First of all, it's on the fragile side. Drop a circuit board when it's not inside a housing of some kind and you'll be lucky if the fiberglass and resin composite sheet doesn't shatter into dozens of sharp pieces. If you were able to decapsulate a silicon chip you'd find it even more fragile than the circuit board it had been soldered to.
There are ways and means to mitigate these drawbacks, of course: the plastic casings of practically all of our tech toys are a cast iron bitch to open to protect the printed circuits inside. Sure, you can fake it for a while without a housing of some kind (in fact, that's how you work on the bench) but if you want your project to last you really should protect it somehow. However, PC boards and plastic cases tend to weigh a fair amount; flexible circuitry has been around since the early 1980's at least but it's tricky to make and not many hobbyists are doing much with it right now. Most flexible circuitry has to be mass produced for consumer goods to be worth the trouble and cost of making. That was until an outfit called Seeed Studio in China started playing with the idea of Arduinos built using flexible circuit boards. Somehow it's only fitting that everybody's favorite microcontroller (well, almost everybody - there will always be people who claim that foo causes cancer) is the first to hit the wires. A quick peek at the specs shows that yes, this is a true blue Arduino, from the Atmel 328 microcontroller at its heart (backward compatible with the 168 if that's the way you roll) to the built in USB interface to the connector layout we all know and love. Unfortunately it's in alpha right now. Structurally speaking it's fragile and will crack if flexed too much and it doesn't have the complement of connectors we're accustomed to. Still, it's a great first start and might have potential if it gets off the ground.
While we're on the topic of flexible objects that can crunch numbers and interact with their environments, here's a noodle baker for you. Researchers at MIT have been working on self folding origami. Rather than paper they're using thin sheets of laminated fiberglass (about half a millimeter in thickness) comprised of regular triangles joined with thin strips of rubber, electrothermal foil actuators to move it around, and bits of flexible circuitry. Power is supplied from the bench with thin leads at this time. The sheets are studded with tiny magnets that fasten sections together once they've moved into position. The first step in the engineering process involves developing an algorithm which describes which sections of material folds in which direction and at what time. Origami figures are folded by following a series of discrete steps so this artform lends itself readily to being described in software. Then it's a matter of the controlling computer turning on the current to the right sequence of leads in the right order to make, say, a boat or a toy plane.
Programmable matter is in a primitive state right now. The power supplies are external and sizable (full sized batteries) and you'd need at a minimum a microcontroller board (like an Arduino) with enough output pins to cover the shape you want to make. That adds a chunk of circuitry about the size of a deck of cards (more or less) and you can't really attach it to the smart-sheet because it would get in the way of the folding process. Also, you'd have to write software for every shape you wanted to (and could) make with a particular smart-sheet. It's going to take a while for the technology to develop to the point where you can select an arbitrary useful shape from a database and do something with it but it has to start somewhere. The mechanism is pretty simple, though, and it won't take much time before hackers start playing with the technology and do interesting things with it (like a self-folding origami rose, which used to be my form of choice).