скачать Mechanical Computation: its Computational Complexity and Technologies Chapter, Encyclopedia of Complexity and Systems Science John H. Reif^{1} Article Outline Glossary I. Definition of the Subject and Its Importance II. Introduction to Computational Complexity III. Computational Complexity of Mechanical Devices and their Movement Problems IV. Concrete Mechanical Computing Devices V. Future Directions VI. Bibliography Glossary Mechanism: a machine or part of a machine that performs a particular task computation: the use of a computer for calculation. Computable: Capable of being worked out by calculation, especially using a computer. The term simulation will be both used to denote the modeling of a physical system by a computer, as well as the modeling of the operation of a computer by a mechanical system; the difference will be clear from the context. ^ Mechanical devices for computation appear to be largely displaced by the widespread use of microprocessorbased computers that are pervading almost all aspects of our lives. Nevertheless, mechanical devices for computation are of interest for at least three reasons: (a) Historical: The use of mechanical devices for computation is of central importance in the historical study of technologies, with a history dating to thousands of years and with surprising applications even in relatively recent times. (b) Technical & Practical: The use of mechanical devices for computation persists and has not yet been completely displaced by widespread use of microprocessorbased computers. Mechanical computers have found applications in various emerging technologies at the microscale that combine mechanical functions with computational and control functions not feasible by purely electronic processing. Mechanical computers also have been demonstrated at the molecular scale, and may also provide unique capabilities at that scale. The physical designs for these modern micro and molecularscale mechanical computers may be based on the prior designs of the largescale mechanical computers constructed in the past. (c) Impact of Physical Assumptions on Complexity of Motion Planning, Design, and Simulation The study of computation done by mechanical devices is also of central importance in providing lower bounds on the computational resources such as time and/or space required to simulate a mechanical system observing given physical laws. In particular, the problem of simulating the mechanical system can be shown to be computationally hard if a hard computational problem can be simulated by the mechanical system. A similar approach can be used to provide lower bounds on the computational resources required to solve various motion planning tasks that arise in the field of robotics. Typically, a robotic motion planning task is specified by a geometric description of the robot (or collection of robots) to be moved, its initial and final positions, the obstacles it is to avoid, as well as a model for the type of feasible motion and physical laws for the movement. The problem of planning such as robotic motion planning task can be shown to be computationally hard if a hard computational problem can be simulated by the robotic motionplanning task. ^ Abstract Computing Machine Models. To gauge the computational power of a family of mechanical computers, we will use a widely known abstract computational model known as the Turing Machine, defined in this section. The Turing Machine. The Turing machine model formulated by Alan Turing [T37] was the first complete mathematical model of an abstract computing machine that possessed universal computing power. The machine model has (i) a finite state transition control for logical control of the machine processing, (ii) a tape with a sequence of storage cells containing symbolic values, and (iii) a tape scanner for reading and writing values to and from the tape cells, which could be made to move (left and right) along the tape cells. A machine model is abstract if the description of the machine transition mechanism or memory mechanism does not provide specification of the mechanical apparatus used to implement them in practice. Since Turing’s description did not include any specification of the mechanical mechanism for executing the finite state transitions, it can’t be viewed as a concrete mechanical computing machine, but instead is an abstract machine. Still it is valuable computational model, due to it simplicity and very widespread use in computational theory. A universal Turing machine simulates any other Turing machine; it takes its input a pair consisting of a string providing a symbolic description of a Turing machine M and the input string x, and simulates M on input x. Because of its simplicity and elegance, the Turing Machine has come to be the standard computing model used for most theoretical works in computer science. Informally, the ChurchTuring hypothesis states that a Turing machine model can simulate a computation by any “reasonable” computational model (we will discuss some other reasonable computational models below). Computational Problems. A computational problem is: given an input string specified by a string over a finite alphabet, determine the Boolean answer: 1 is the answer is YES, and otherwise 0. For simplicity, we generally will restrict the input alphabet to be the binary alphabet {0,1}. The input size of a computational problem is the number of input symbols; which is the number of bits of the binary specification of the input. (Note: It is more common to make these definitions in terms of language acceptance. A language is a set of strings over a given finite alphabet of symbols. A computational problem can be identified with the language consisting of all strings over the input alphabet where the answer is 1. For simplicity, we defined each complexity class as the corresponding class of problems.) Recursively Computable Problems and Undecidable Problems. There is a large class of problems, known as recursively computable problems, that Turing machines compute in finite computations, that is, always halting in finite time with the answer. There are certain problems that are not recursively computable; these are called undecidable problems. The Halting Problem is: given a Turing Machine description and an input, output 1 if the Turing machine ever halts, and else output 0. Turing proved the halting problem is undecidable. His proof used a method known as a diagonalization method; it considered an enumeration of all Turing machines and inputs, and showed a contradiction occurs when a universal Turing machine attempts to solve the Halting problem for each Turing machine and each possible input. Computational Complexity Classes. Computational complexity (see [LP97]) is the amount of computational resources required to solve a given computational problem. A complexity class is a family of problems, generally defined in terms of limitations on the resources of the computational model. The complexity classes of interest here will be associated with restrictions on the time (number of steps until the machine halts) and/or space (the number of tape cells used in the computation) of Turing machines. There are a number of notable complexity classes: P is the complexity class associated with efficient computations, and is formally defined to be the set of problems solved by Turing machine computations running in time polynomial in the input size (typically, this is the number of bits of the binary specification of the input). NP is the complexity class associated with combinatorial optimization problems which if solved can be easily determined to have correct solutions, and is formally defined to be the set of problems solved by Turing machine computations using nondeterministic choice running in polynomial time. ^ is the complexity class is defined to be set of problems solved by Turing machines running in space polynomial in the input size. EXPTIME is the complexity class is defined to be set of problems solved by Turing machine computations running in time exponential in the input size. ^ and PSPACE are widely considered to have instances that are not solvable in P, and it has been proved that EXPTIME has problems that are not in P. Polynomial Time Reductions. A polynomial time reduction from a problem Q’ to a problem Q is a polynomial time Turing machine computation that transforms any instance of the problem Q’ into an instance of the problem Q which has an answer YES if and only if the problem Q’ has an answer YES. Informally, this implies that problem Q can be used to efficiently solve the problem Q’. A problem Q is hard for a family F of problems if for every problem Q’ in F, there is a polynomial time reduction from Q’ to Q. Informally, this implies that problem Q can be used to efficiently solve any problem in F. A problem Q is complete for a family F of problems if Q is in C and also hard for F. ^ He will later consider various mechanical problems and characterize their computation power:
The simulation proofs in either case often provide insight into the intrinsic computational power of the mechanical problem or mechanical machine. ^ There are a number of abstract computing models discussed in this Chapter, that are equivalent, or nearly equivalent to conventional deterministic Turing Machines.
There are also a number of abstract computing models that appear to be more powerful than conventional deterministic Turing Machines.
^ Complexity of Motion Planning for Mechanical Devices with Articulated Joints The first known computational complexity result involving mechanical motion or robotic motion planning was in 1979 by Reif [R79]. He consider a class of mechanical systems consisting of a finite set of connected polygons with articulated joints, which are required to be moved between two configurations in three dimensional space avoiding a finite set of fixed polygonal obstacles. To specify the movement problem (as well as the other movement problems described below unless otherwise stated), the object to be moved, as well as its initial and final positions, and the obstacles are all defined by linear inequalities with rational coefficients with a finite number of bits. He showed that this class of motion planning problems is hard for PSPACE. Since it is widely conjectured that PSPACE contains problems are not solvable in polynomial time, this result provided the first evidence that these robotic motion planning problems not solvable in time polynomial in n if number of degrees of freedom grow with n. His proof involved simulating a reversible Turing machine with n tape cells by a mechanical device with n articulated polygonal arms that had to be maneuvered through a set of fixed polygonal obstacles similar to the channels in Swisscheese. These obstacles where devised to force the mechanical device to simulate transitions of the reversible Turing machine to be simulated, where the positions of the arms encoded the tape cell contents, and tape read/write operations were simulated by channels of the obstacles which forced the arms to be reconfigured appropriately. This class of movement problems can be solved by reduction to the problem of finding a path in a O(n) dimensional space avoiding a fixed set of polynomial obstacle surfaces, which can be solved by a PSPACE algorithm due to Canny [C88]. Hence this class of movement problems are PSPACE complete. (In the case the object to be moved consists of only one rigid polygon, the problem is known as the piano mover's problem and has a polynomial time solution by Schwartz and Sharir [SS83].) ^ There were many subsequent PSPACE completeness results for mechanical devices (two of which we mention below), which generally involved multiple degrees of freedom:
There are two classes of mechanical dynamic systems, the Ballistic machines and the Browning Machines described below, that can be shown to provide simulations of polynomial space Turing machine computations. ^ A ballistic computer (see Bennett [B82, B03]) is a conservative dynamical system that follows a mechanical trajectory isomorphic to the desired computation. It has the following properties:
Collisionbased computing [A01] is computation by a set of particles, where each particle holds a finite state value, and state transformations are executed at the time of collisions between particles. Since collisions between distinct pairs of particles can be simultaneous, the model allows for parallel computation. In some cases the particles can be configured to execute cellular automata computations [JS+01]. Most proposed methods for Collisionbased computing are ballistic computers as defined above. Examples of concrete physical systems for collisionbased computing are:
^ In a mechanical system exhibiting fully Brownian motion, the parts move freely and independently, up to the constraints that either link the parts together or forces the parts exert on each other. In a fully Brownian motion, the movement is entirely due to heat and there is no other source of energy driving the movement of the system. An example of a mechanical systems with fully Brownian motion is a set of particles exhibiting Browning motion, as say with electrostatic interaction. The rate of movement of mechanical system with fully Brownian motion is determined entirely by the drift rate in the random walk of their configurations. Other mechanical systems, known as driven Brownian motion systems, exhibit movement is only partly due to heat; in addition there is a driving there is a source of energy driving the movement of the system. Example a of driven Brownian motion systems are:
There is no energy consumed by fully Brownian motion devices, whereas driven Brownian motion devices require power that grows as a quadratic function of the drive rate in which operations are executed (see Bennett [B03]). Bennett [B82] provides two examples of Brownian computing machines:
