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