Abstract:
This Thesis documents our explorations of simple natural physical systems that exhibit useful, interesting computational effects. We view such physical systems as specialized “computers”/natural–computers. These natural–computers (physical systems), as they evolve in phase space, can be seen as performing a computation or executing a natural algorithm to solve a specific problem. We often consider
systems that apparently “solve” problems that are hard to solve by using conventional computers. We actually view the physical systems themselves—not their numerical simulations—as computers.
The Thesis is a braid of three ideas/inventions: (i) A gravity powered
“computer”—constructed out of beads and rods of an abacus—that can perform data processing tasks like sorting, searching, etc. in O(√
N) time on an unsorted database of size N. (ii) Bilateral Computing, a paradigm for the construction of natural physical computing devices which are “bilateral” in nature: devices realizing a certain function f can spontaneously compute as well as invert f. These gadgets can be used to solve NP–hard problems like Boolean Satisfiability (SAT), apparently without using an exponential amount of resources. (iii) Balance Machine, a generic natural computational model which is shown to be universal. First of all, natural algorithms for sorting and searching—trivial problems that can be solved by classical computing methods quite efficiently, using only resources (for instance, time and memory) polynomial in the size of the input data—are developed.
These, while serving as typical examples of natural algorithms, set the
stage for natural algorithms solving hard problems. It may be noted, however, that these natural algorithms—the physical processes themselves, and not their various implementations—do outperform their classical counterparts in a spectacular way! These natural algorithms are “run” on an abacus–like natural–computer powered by
gravity. We move on to solve computationally hard problems: We attempt to solve SAT, an NP–complete problem, using a natural–computer constructed with pipes and pistons, which uses water levels to encode data. Besides proposing a specialized natural–computer that solves SAT, we develop a general paradigm—referred to as Bilateral Computing—advocating the design of a class of such “bilateral” natural–computers; these are physical systems in which there is no intrinsic distinction between its various parameters: there is no tag attached to each of the parameters classifying it as an
“input parameter” or as an “output parameter”. In other words, one has the freedom to change, or assign a value to, any of the parameters and watch what happens to the rest. When one or more of the parameters is varied, the system will react by spontaneously adjusting the rest of the parameters so as to maintain a certain relation between the various parameters. The culmination of our research is a universal, generic natural computational model. This model, called Balance Machine, is a mechanical model like a Turing Machine, which can be directly realized in the form of a machine. It consists of iii components that resemble ordinary physical balances, each with a natural tendency to automatically balance their left and right pans: If we start with certain fixed weights, that represent inputs, on some of the pans, then the balance–like components would vigorously try to balance themselves by filling up the rest of the pans with suitable weights that represent the outputs. Interestingly, the balance machine is a bilateral
computational model. Natural algorithms exploit the vast computing power in ordinary, commonplace physical phenomena which occur in the familiar macroscopic world unlike other popular approaches to unconventional computing that feed on sophisticated processes in
molecular biology and quantum mechanics. The very fact that natural algorithms are “extracted” from easy–to–understand natural physical phenomena witnessed everywhere by everyone (and not only in laboratories by specialists) endows it with great pedagogical value, among other things. Finally, there is a whole new side to Natural Algorithms other than building practicable natural–computers: It inspires researchers to look at computation in a new light, to think and talk about computation in terms of a new “vocabulary” comprising natural physical processes as opposed to a set of logical operations. Natural–computers may or may not become practical computing gadgets of the future, but we believe that the new way of thinking will certainly persist.