Introduction

An amorphous computer is a large network of simple, expendable and unreliable computing units, identically programmed, and distributed geometrically across a given domain. These computing units, which we will call “cells”, similar to their biological counterparts, only interact locally, and are not centrally controlled. The concept of an amorphous computer has become increasinly more interesting to the computer science community in recent years. It has been suggested that using this decentralized network of computers could have applications in computation and processor design, and even to accomplish physical tasks as in nanotechnology.

Recently, there has been some work on the problem of amorphous shape-compilation. Assume we have a sheet of amorhphous cells (possibly a growing sheet), and a shape of some kind is given to us. We must create a set of instructions to tell our cells how to produce such a shape, so that all of the cells in the interior of the shape are in one state, and the others are in another state. Attila Kondacs produced a construction to solve such a problem. His method involved packing the shape with discs, and producing a network of “disc-centers” with known disc radii. The growth process involved recreating these disc-centers using triangulation, and then “switching on” cells that were within the disc-radius from it's corresponding disc center.

This provides a very nice solution. However, it still required a reliance on the individual disc-centers. In the even that a disc-center were to malfunction or die, other centers would have to become aware of its death and attempt to find a suitable replacement. This process was slow and occasionally unreliable. A better solution would not require behavior of any given cell, but would only require behavior of the system globally.

Amorphous Computing and Laplace's Equation

An observation that was pointed out to me by Professor Gerry Sussman and Daniel Coore is that an Amorphous Computer can be used to solve a very particular Partial Differential Equation: Laplace's equation. That is, assume we have a 2D sheet of amorphous computing units that are evenly distributed. Assume also that cells lying on some closed curve C are assigned real-number values that are “continuous” around C. Our amorphous computer can now determine values within C, giving an approximate solution to the unique harmonic function which extends to the interior of C.

The process of solving for the interior values in relatively trivial. First, the interior cells assume some initial value, say 0. Then, every cell performs the following task. Let p be any cell. To start, p obtains the values from every nearby cell. Then, p takes the averages of all of these values, call this average A, and sets its own value to A. When the system stabilizes, every cell have a value which will be exactly the average value of it's neighbors, thus the divergence of this function will be 0. It will, therefore, be a solution to Laplace's equation in the interior of C.

This solution is, in fact, very precise. For example, here is a method for cells in a square region to determine their global coordinates. Let's assume we have a square domain of cells. Furthermore, we can assume that cells on the borders are given their global coordinates (cells that lie on borders have an easy time determining their coordinates, because they can “ping” the corner-cells, and determine how many hops away they are). Now, we have two harmonic functions on the border cells: u(x,y) = x and v(x,y) = y. We can solve these equations as described above, which will extend u and v to the entire region. The values we get for u will approximate x, and those for v will approximate y. The following image shows such a grid in which the border cells are black. Every cell for which u^2 + v^2 < k, for some k, is colored green.

This ability of using border values to store global information is very powerful. Let me mention several reason why this is the case:

1. It is robust to random cell death. That is, if a few cells were to stop functioning, it doesn't affect the global behavior of the system. Most importantly, no given cell needs to be reliable.

2. It is very easily scalable, in the sense that we may want to start using a much larger number of cells in a much large grid, with a simple transformation of the intial system (mapping border values from the small grid to the large grid).

3. Adding more layers of complexity, i.e. computing solutions to several harmonic functions simultaneously, does not have a substantial affect on the overall speed of computation.

Application: Storing Shapes using Complex Analytic Functions

Recall that holomorphic functions are composed of two coordinate functions that are both harmonic. I have utilized this fact in the following shape-compilation method:

Assume we are given a 2 dimensional region R, with a smooth boundary B, that we would like to “grow” inside of our amorphous grid. Let the complex unit circle be U = {u : |u| <= 1}.

1. Take a map F = u + iv which conformally maps the R onto U.

2. Once we have done this, we can extend F (uniquely, because our function is analytic) to a larger region so that it can cover an entire square grid of cells. We now have a complex function that gives us values for u and v, most importantly, on the grid boundary.

3. Store values for each coordinate function on every boundary cell (i.e. every cell on the boundary has a u-value and a v-value).

4. As described above, if we know values of a given function on the boundary of an amorphous grid, we can find a harmonic solution on the interior using our “averaging process”. We now perform this on both coordinate functions, we will have reconstructed u and v, and therefore F, as desired. The shape is now defined in the following way: a given cell is defined to be “in the interior of the shape” if u^2 + v^2 < 1.

The details of such this construction, and particularly in the creation and extension of F, are described in greated detail in a paper I am working on.