Abstract

«There's Plenty of Room at the Bottom», said the title of Richard Feynman's 1959 visionary conference at the California Institute of Technology. Fifty years on, the development of nanotechnologies has led computer scientists to pay close attention to the links between physical reality and information processing. Not all the physical requirements of optimal computation are captured by traditional models - one still missing is reversibility. The dynamical laws of physics are reversible at microphysical level, distinct initial states of a system leading to distinct final states. On the other hand, as von Neumann already conjectured, irreversible information processing is expensive: to erase a single bit of information costs ~3 × 10-21 joules at room temperature. Information entropy is a thermodynamic cost, to be paid in non-computational energy dissipation. As nanotechnologies evolve, it is reasonable to conjecture that this discrepancy is to become a decisive technical issue the future of computation. This paper addresses the problem drawing on Fredkin's Finite Nature hypothesis: the ultimate nature of the universe is discrete and finite, ontologically satisfying the axioms of classical, atomistic mereology. It is shown that a world made only of atoms in a lattice, capable of instantiating a minimal number of well-defined basic properties, allows for the strongest isomorphism between matter and information. The chosen model is a cellular automaton (CA) with strongly reversible dynamics, capable of retaining perfect memory of the totality of information present at the beginning of the universe. It is shown that such a CA can implement the Boolean logical operations and the other building bricks of computation: it may be used to develop and host all-purpose computers - universal Turing machines capable of computing, by Turing's Thesis, anything computable. Our model is therefore a candidate for the realization of high-performance computational systems, capable of exploiting the resources of the physical world in the most efficient way, for they can host logical circuits with internal energy dissipation virtually close to zero.