Homepage RC
Invited Talks

Invited Talks

For a full schedule, including dates and times of all talks listed below, please see the Programme.

Michael P. Frank
Center for Computing Research, Sandia National Laboratories, USA

Physical Foundations of Landauer's Principle

We review the physical foundations of Landauer's Principle, which relates the loss of information from a computational process to an increase in thermodynamic entropy. Despite the long history of literature addressing the Principle, its fundamental rationale and proper interpretation remain frequently misunderstood. Contrary to some misinterpretations of the Principle, merely transferring entropy between a computational subsystem and a non-computational one can be done in a thermodynamically reversible way, and does not necessarily result in any increase in total entropy. However, properly understood, Landauer's Principle is not really a statement about general transfers of entropy; rather, it is more specifically concerned with the ejection of a correlated state (or a portion thereof) from a controlled, computational form (e.g., a computed bit) to an uncontrolled, non-computational form, i.e., as part of a thermal environment. Any uncontrolled, thermal environment will, by definition, continually re-randomize the physical information that it contains, given our perspective as non-omniscient observers who lack the ability to precisely model and track the exact dynamical evolution of the microstates of such environments. Therefore, any correlations that exist involving any information that is ejected into and subsequently thermalized by the environment will be lost from our perspective, resulting directly in an irreversible increase in thermodynamic entropy. Avoiding the ejection and thermalization of correlated computational information motivates moving to the reversible computing paradigm, although the requirements for computations to be thermodynamically reversible are less restrictive than frequently described, particularly in the case of stochastic computational operations. There exists a rich space of possibilities for the design of computational processes that utilize stochastic, many-to-one computational operations while nevertheless avoiding net entropy increase that remains to be fully explored.

Ivan Lanese
Focus Team, University of Bologna/INRIA

From Reversible Semantics to Reversible Debugging

We present a line of research in reversible computing for concurrent systems. This line of research started in 2004 with the definition of the first reversible extensions for concurrent process calculi such as CCS, and is currently heading to the production of practical reversible debuggers for concurrent languages such as Erlang. Main questions that had to be answered during the research include the following. Which is the correct notion of reversibility for concurrent systems? Which history information needs to be stored? How to control the basic reversibility mechanism? How to exploit reversibility for debugging? How to apply reversible debugging to real languages?

Norman Margolus
Massachusetts Institute of Technology, USA

Finite-State Classical Mechanics

Reversible lattice dynamics embody basic features of physics that govern the time evolution of classical information. They have finite resolution in space and time, don't allow information to be erased, and easily accommodate other structural properties of microscopic physics, such as finite distinct state and locality of interaction. In an ideal quan- tum realization of a reversible lattice dynamics, finite classical rates of state-change at lattice sites become equivalent to finite classical energies and momenta. This is very different than traditional continuous mod- els of classical dynamics, where the number of distinct states is infinite, the rate of change between distinct states is infinite, and energies and momenta are not tied to rates of distinct state change. Here we discuss a family of classical mechanical models that have the informational and energetic realism of reversible lattice dynamics, while retaining the conti- nuity and mathematical framework of classical mechanics. These models may help to clarify the informational foundations of mechanics.

Nicolas Ollinger
Univ. Orléans, INSA Centre Val de Loire, Orléans, France

On Aperiodic Reversible Turing Machines

A complete reversible Turing machine bijectively transforms configurations consisting of a state and a bi-infinite tape of symbols into another configuration by updating locally the tape around the head and translating the head on the tape. We discuss a simple machine with 4 states and 3 symbols that has no periodic orbit and how that machine can be embedded into other ones to prove undecidability results on decision problems related to dynamical properties of Turing machines.

Social Event Talk

In addition, there will be the following talk at the social event at the National Space Centre on Thursday, 13th of September.

Edward F. Fredkin
Carnegie Mellon University, Pittsburgh, PA 15213, USA

Discrete Space-Time-State Physics

Consider that, perhaps, the most microscopic elements of space, time and all of the other basic measures in physics are discrete. We certainly have no evidence to the contrary. What this could mean is that there would be natural units of length and time. If so, every actual interval of time could be exactly represented by an integer.

If we further suppose that, instead of true randomness at the level of quantum mechanics (QM), we substitute ''Unknowable Determinism'' or UD, where, at the level of QM, we replace the ''random'' by the continual influx of unknowable, microscopic information that pours into every QM event, from every direction. The unknowable information must, if this model is to correspond to reality, be essentially unaffected by any physical aspects that we can measure.

The idea is to have a model of a microscopic system where physical events are actually deterministic, but that nevertheless, appear as random to observers from within the system. A given system could have unknowable determinism which could appear just as unpredictable, to those within that system, as does true randomness. There would be no way, in general, to reliably predict the exact future of the microscopic states of any actual region. There is a simple explanation for that impossibility. Aside from consequences of laws of physics, including conservation laws, there may be many detailed microscopic states that each correspond to what can be measured macroscopically. The nature of exact reversibility and exact conservation laws are such as to impose the laws of probabilistic QM on our higher-level observations despite the possibility that underlying the apparent randomness is strict determinism at the most microscopic levels. Thus it may be that the QM process is actually deterministic, but a more appropriate description might be ''Unknowable Determinism.''

It's not that microscopic physics requires a non-deterministic explanation; rather, it could be that our knowledge and understanding of exactly what is happening in the actual real microscopic world is what is necessarily uncertain.

Imagine a model of the most microscopic state with space being a 3+1 dimensional regular Cartesian array of cells, where, at each instant of discrete time, each cell is in one of a small integer number of states (such as 3). If we assign integer coordinates (x, y, z, t) to the 2nd-order space-time coordinates of each of the most microscopic cells, then x+y+z+t can be thought of as always being an even number. Of course, the x,y and z coordinates must range over the size of the Universe, but the static range of the t coordinate is 2, the present time and the immediate prior time. This second-order array allows for the convenient static representation of dynamic information.

Our hypothesis is that the process that is the most microscopic discrete physics (perhaps underlying QM) could correspond exactly to the temporal evolution of state of some such discrete, deterministic system. Instead of randomness, at the bottom we might have Unknowable Determinism. Every correct picture of the actual microscopic state cannot be calculated by us until after it has arrived, naturally.

An advantage of such reversible systems to their creators is that after the detection of an extraordinary event, the process can be reversed to enable efficient study of the exact cause.