Abstract:
The Balance Machine is a newly proposed natural computational model that
consists of components resembling physical balances. The model has only one
operation, “balancing", which suffices in principle to perform universal computation.
An interesting feature of the balance machine is its bidirectional operation:
it can compute “forwards and backwards", i.e. both a function and its
partial inverse can be computed spontaneously using the same machine. Also,
the machine exhibits a different kind of parallelism – a “bilateral parallelism".
The aim of this note is two-fold: To introduce a formalism for computing
with balance machines – a convenient notation for representing the mechanical
model on paper, and to demonstrate its expressive power by solving two
NP{complete problems, namely, Set Partition and Knapsack