首页    期刊浏览 2025年02月28日 星期五
登录注册

文章基本信息

  • 标题:A Physically Universal Cellular Automaton
  • 本地全文:下载
  • 作者:Luke Schaeffer
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    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.

  • 关键词:cellular automata ; Reversible Computation ; universality
国家哲学社会科学文献中心版权所有