Reversible computing and cellular automata - A survey
Reversible computing and cellular automata - A survey
复制标题
DOI：
10.1016/j.tcs.2008.01.041
复制
发表时间：
2008-04
期刊：
影响因子：
--
通讯作者：
K. Morita
中科院分区：
文献类型：
--
作者：
K. Morita
可逆计算是一种范式，其中定义了计算模型，以便它们反映物理可逆性，这是自然界基本的微观物理属性之一。在这篇综述/教程论文中，我们讨论了如何在可逆系统中进行计算，如何通过可逆逻辑元件构建通用可逆计算机，以及这些逻辑元件如何与可逆物理现象相关。我们将看到，在可逆系统中，计算通常可以以与常规非常不同的方式进行（即，不可逆）计算系统，甚至非常简单的可逆系统或逻辑元件都具有计算或逻辑通用性。我们讨论这些问题的基础上可逆逻辑元件/电路，可逆图灵机，可逆细胞自动机，以及其他一些相关的模型的可逆计算。
Reversible computing is a paradigm where computing models are defined so that they reflect physical reversibility, one of the fundamental microscopic physical property of Nature. In this survey/tutorial paper, we discuss how computation can be carried out in a reversible system, how a universal reversible computer can be constructed by reversible logic elements, and how such logic elements are related to reversible physical phenomena. We shall see that, in reversible systems, computation can often be carried out in a very different manner from conventional (i.e., irreversible) computing systems, and even very simple reversible systems or logic elements have computation- or logical-universality. We discuss these problems based on reversible logic elements/circuits, reversible Turing machines, reversible cellular automata, and some other related models of reversible computing.