Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-084 | 12th June 2014 00:53

A Physically Universal Cellular Automaton

RSS-Feed




TR14-084
Authors: Luke Schaeffer
Publication: 20th June 2014 20:20
Downloads: 5937
Keywords: 


Abstract:

Several cellular automata (CA) are known to be universal in the sense that one can simulate arbitrary computations (e.g., circuits or Turing machines) by carefully encoding the computational device and its input into the cells of the CA. In this paper, we consider a different kind of universality proposed by Janzing. A cellular automaton is physically universal if it is possible to implement any transformation on a finite region of the CA by initializing the complement of the region and letting the system evolve. We answer an open problem of Janzing by constructing an example of a physically universal CA.



ISSN 1433-8092 | Imprint