Algorithms and computation are at the heart of everything. When cells obey the program in DNA they make a human - but how can they all be following the same instructions and yet do different things? This is the question explored in this video - and if you only watch one video this year make sure it is this one.

Its title is 

Tilt: The Video — Designing Worlds to Control Robot Swarms with only Global Signals 

and this could leave you feeling confused as to what it is all about. No doubt lots of people have just passed it by on the grounds it is something esoteric to do with robot swarms. It sort of is, but it has a much wider importance and appeal.

The problem that it attempts to solve is how can you get general computation from a swarm of identical units all receiving identical instructions.

There are some obvious distributed parallel programs. For example, if you imagine that each pixel in a black and white image is a computational unit, then you could give the instruction "all white pixels next to a black pixel please put up your hand". If pixels had hands what you would see is the edge of any object.

This is fine but somehow nature achieves much more complex distributed parallel computation. All of the cells in an animal start out the same and in roughly the same environment and they are all running the same program, so how do they end up different? The answer is probably related to the environment in which they develop.

What Aaron Becker and his team has done is to work out how simple computational units can occupy a landscape that results in them doing general computation.  Each unit carries out the program go up, go right, go down, go left. The movements are not single steps, but as far as each unit can go.

Now watch at least the first part of the video: 

Notice that each block carries out the program simply because the board is tilted in each direction in turn. In other physical systems the "force" that makes the entities move could be anything from chemical to light seeking. 

The key idea is the implementation of the basic logic gates:

Once you understand how this works you can start to unravel the other programs.

The fact that this computational scheme is Turing complete more or less follows from the existence of the universal gates - NAND or NOR.

The video then goes on to show that things get complex very quickly with a proof that the decision tree problem, finding a set of inputs that produces a single output, is NP hard. Not surprising, but it suggests something about the complexity of other distributed parallel tasks. 

Next we have an implementation of matrix permutation, which then leads on to a bubble sort - yes a bubble sort!

The final part of the video explains why fan-out gates are difficult, even impossible, if you restrict yourself to fixed blocks. To create a fan-out gate you need a moving block as part of the landscape.

Once you have a fan-out you can build a full adder and the example given is a counter.

There are so many possibilities here and so many questions. Simple sliding blocks are universal for computation. Given the right environment they are Turing complete and you can build any computer you care too.

There seems to be a connection with cellular automata.

And who will be first to build a sliding block computer in Minecraft?

Computation really is everywhere.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info