The Minion Machine
August 9, 2013 § 1 Comment
The Action of Complexity
Draft 2, Ernest Prabhakar, 2013-08-07
Inspired by a proposal from Christy Warren
The Premise
Using concepts derived from physics such as Energy and Time, we can gain insight into the nature of computational complexity.
The Goal
Devise the simplest possible physical system that captures the aspects of computation relevant to complexity theory.
The Concept
The goal is to move the objects from an initial ordering I to final ordering F while consuming the least amount of time and energy. Importantly, the only way to accomplish this task is by giving commands to the minions. Minions only understand commands of the form “Minion – Starting Bin – Direction – Distance”.
The Model
We start by making a number of simplifying assumptions. These can be revisited later as needed.
- The energy required for the minions to live and move themselves is either negligible or from an external source. The only energy we care about is that required to i) move the objects and ii) communicate with the minions.
- All objects have significant mass (so it takes energy to move them) but negligible size (so we don’t need to worry about collisions).
- All objects have the same mass m0 and top speed v0. The array has negligible friction, and the distance between bins is very large compared to the distance required to accelerate to top speed. This allows us to assume that moving any object from one bin to another takes the same amount of energy (to accelerate & decelerate):
E0 = m0 v0^2
but a varying amount of time, proportional to the distance x:
t = x / v0
- The communicator uses something like FM modulation, which requires energyE_c and time t_c both proportional to the dimensionless size S of the command, e.g. in bits:
E_c = a S t_c = b S
The sizes N and M are fixed, so we can specify that all primitive commands use a fixed-width bitfield of size S0:
S0 = log(M)+ log(N) + 1 + log(N)
Metrics
Say that it takes n steps to obtain the desired order. The distance traversed by each step is given by x_i, which can be summed and divided by n to get the average distance d.
Assuming serialized movements with no latency between them gives:
Energy = n a S0 + n E0 = n (a S0 + E0)
Time = n b S0 + n d / v0 = n (S0 + d/v0)
We can multiply these to get the action:
Action = Energy * Time = n^2 (a S0 + E0 ) (b S0 + d/v0)
Since S0 is dimensionless, we can pull all the dimensions in a new constant h, which is the per bit action of the communicator:
h = a b
giving us new dimensionless constants:
e = E0 / a f = d / (b v0)
allowing us to write:
Action = n^2 h (S0 + e)(S0 + f) = n^2 h (S0^2 + 2(e + f)S0 + e f)
Interpretation
The action can be interpreted as a measure of the effort required to ‘disentangle’ a system from an initial ordering I to final ordering F.
The constant e is the ratio between the energy required for each step of movement (E0) and that for each bit of control (a).
The constant f is the ratio between the average time required for each step of movement (d/v0) and that to send each bit of control (b).
Which tells us that the effort is primarily determined by:
- Movement, when e + f >> 1
- Control, when e + f << 1
- Energy, when e >> f
- Time, when f >> e
While those are perhaps obvious, this model also provides a precise way to measure the effort (action) in intermediate cases where e and f are comparable to 1 and each other. It also gives us a mathematical formalism that can be used to minimize the action when varying some of the constants or extending the action.
Questions
- Is the action the right way to combine E and t? What are the alternatives, and their advantages and disadvantages?
- Right now having more minions doesn’t help (or hurt). What happens if we include their energy cost, but allow them to perform actions in parallel? What if we are allowed (at some cost) to send the same command to multiple minions at once?
- What if the energy cost is dependent the distance between bins, rather than constant?
- What is the physical interpretation of h e f, the “pure movement” action d E0 / v0?
Conclusion
This model leads to a natural and interesting definition of action for computational systems that bears some interesting similarities to the idea of ‘complexity’. To flesh this out, however, would require a mechanism for encoding (and costing) higher-order algorithms such as “sort the array”, rather than merely “move these objects between bins”.
iHack, therefore iBlog 
[…] The Sequel to “The Minion Machine“ […]