Hi all,
today we will hear from Dominik Janzing, who is visiting this week
from Tübingen. He'll tell us about physically universal cellular
automata --- see below for full title and abstract. I know Dominik
from way back and it always struck me that he is very good at figuring
out the most interesting and important questions to ask, and I expect
this talk will be in the same spirit. See you there!
Best,
-joe
Title:
Physically universal cellular automata and Hamiltonians as models for
a thermodynamic theory of control
Abstract:
I propose to study the thermodynamic cost of computation and control
via 'physically universal' cellular automata or Hamiltonians [1]. I
defined them as
spatially homogeneous systems that admit the implementation of any
desired transformation on any finite target region by first
initializing the state of its
surrounding and then letting the system evolve according to its
autonomous dynamics.
This way, one obtains a model in which the boundary between controller
and system to be controlled can be arbitrarily shifted and every
subsystem can play both roles.
In a nutshell, the thermodynamic cost of an operation is then given by
the size of the region around the target region that needs to be
initialized.
In the meantime, physically universal CAs have been constructed by
Schaeffer [3,4] and Salo & Toermae [5]. Here I show that for those
CAs the cost for
implementing n operations grows linearly in n, while operating in a
thermodynamic cycle would require sublinear growth in order to ensure
zero cost per operation
in the limit n to infinity. Likewise, the simple task of information
storage requires non-zero information cost per time in these CAs.
Whether this property is unique to
these particular CAs or whether it holds for every physically
universal CA has to be left to future research. After all, physical
universality implies
instability of information, which could result in fundamental lower
bounds for the cost of information storage.
References:
[1] D. Janzing: Is there a physically universal cellular automaton or
Hamiltonian? arXiv:1009.1720
[2] S. Aaaronson: A physically universal cellular automaton,
Shtetl-Optimized, the Blog of Scott Aaronson, 2014
[3] L. Schaeffer: A physically universal cellular automaton. ECCC, 2015
[4] L. Schaeffer: A physically universal quantum cellular automaton, CA&DCS 2015
[5] V. Salo, I. Tormae: A one-dimensional physically universal
cellular automaton, arXiv:1501:03988