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 noncomputational 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, noncomputational
form, i.e., as part of a thermal environment. Any uncontrolled, thermal
environment will, by definition, continually rerandomize the physical
information that it contains, given our perspective as nonomniscient
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, manytoone 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
FiniteState 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
statechange 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 biinfinite 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 SpaceTimeState 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 higherlevel 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 nondeterministic 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
2^{nd}order spacetime 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 secondorder 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.
