It is shown how information contained in the pair-wise correlations between atoms of a gas can be used to convert completely heat taken from a thermostat into mechanical work in a process of relaxation of the system to its thermal equilibrium state. Both classical correlations and quantum correlations (entanglement) are considered. The amount of heat converted into work is proportional to the entropy defect of the initial state of the system. The equivalence relation between information and work is explicitly demonstrated for the case of two-particle correlations. The amount of work obtained per particle is twice as large in the case of entanglement as in the case of classical correlations.

Since reversible computing requires preservation of all information throughout the entire computational process, it implies that all the errors that appear as a result of the interaction of the information-carrying system with uncontrolled degrees of freedom must be corrected. This can only be done at the expense of an increase in the entropy of the environment corresponding to the dissipation of the "noisy" part of the energy of the system in the form of heat. This paper gives an expression of that energy in terms of the effective noise temperature, and calculates the relationship between the energy dissipation rate and the rate of computation

Fine-grained, indefinitely-extended mesh architectures, which can aptly be termed ‘Programmable Matter’, play a complementary rather than competitive role vis-à-vis traditional architectures. Ideal areas of applicability are physical modeling, materials science, interactive modeling of complex objects, image processing, and pattern recognition. Moreover, these architectures are well suited to furnish a viable blueprint for computers built out of atomic-scale components, towards which technology is inexorably leading. In spite of a potentially huge performance gain over conventional computers, programmable matter is currently hard to exploit. In most cases, its raw computational resources do not directly match the structure of problems one might want to apply it to. Since much ad hoc programming is needed to attain a reasonable fraction of the theoretical performance, so far only niche applications have been explored. We are developing a modeling methodology that will give programmable matter a much broader scope of application. This methodology makes extensive use of synthetic dynamics inspired by physics (kinematic transformations, cellular automata and lattice gases, statistical–mechanical ensembles, simulated annealing, simulated staining, texture-locked loops, etc.), but harnesses these dynamics to data-processing tasks of a more general nature as are encountered in a variety of mundane applications. In particular, by means of suitable feedback, the massive pattern-generation resources of cellular automata machines are used to construct flexible pattern recognizers.

We show that a rotation in three dimensions can be achieved by a composition of three shears, the first and third along a specified axis and the second along another given axis orthogonal to the first; this process is invertible. The resulting rotation algorithm is practical for the processing of fine-grained digital images, and is well adapted to the access constraints of common storage media such as dynamicRAMor magnetic disk. For a 2-D image, rotation by composition of three shears is well known. For 3-D, an obvious nine-shear decomposition has been mentioned in the literature. Our three-shear decomposition is a sizable improvement over that, and is the best that can be attained—just two shears won't do. Also, we give a brief summary of how the present three-shear decomposition approach generalizes to any linear transformations of unit determinant in any number of dimensions.

The length of the longest dead path (LLDP) is a widely used parameter in estimating the efficiency of branch-and-bound optimization algorithms that employ the LIFO exploration schema.Thanks to two original theorems, we are able to present a particularly attractive procedure for determining the LLDP.In fact, this procedure requires a number of storage variables that are independent ofproblem size and very small; moreover, the procedure is selfcontained in the sense that it can be externally attached to any LIFO branch-and-bound program without interfering with its algorithms and data structures.

The theory of reversible computing is based on invertible primitives and composition rules that preserve invertibility. With these constraints, one can still satisfactorily deal with both functional and structural aspects of computing processes; at the same time, one attains a closer correspondence between the behavior of abstract computing systems and the microscopic physical laws (which are presumed to be strictly reversible) that underly any concrete implementation of such systems. According to a physical interpretation, the central result of this paper is that it is ideally possible to build sequential circuits with zero internal power dissipation . These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.