Reversible Computing as a Future Computing System

点击翻译按钮获取中文摘要

Recently, much attention has been paid on so-called "Natural computing systems" like quantum computing and DNA computing. Reversible computing is also such a paradigm that has a property analogous to physical reversibility, and is closely related to quantum computing. It is a very important computing model to investigate the possibilities of future computing systems, and now is the time to make foundational and extensive researches on it for the future. From this standpoint, we studied various reversible computing systems and some other related systems, and obtained the following results.(1)A universal reversible logic element called "rotary element" is proposed, and a novel architecture for reversible computers based on it is shown. Such a computer works in a very different way than a conventional computer, and gives a new insight into reversible computing.(2)Universal reversible cellular automata having very simple transition functions in which rotary elements can be embedded are given. This shows reversible computing systems can be built based on extremely simple reversible rules.(3)Cellular automata having number-conserving property is studied, This property is an analogue of conservation law of mass or energy in physics, and has a close relation to reversibility. Simple models of such systems having computation-universality is shown.(4)It is shown that self-reproduction like living things is possible in reversible and number-conserving cellular automata.(5) Hyperbolic cellular automata, which are another model of physical space, is studied. It is shown that such systems have computing ability of high efficiency.(6)Several uniquely parsable grammar systems are studied. These systems can be regarded as kinds of asynchronous reversible systems. Various properties on them, relations to cellular automata, normal forms, and their pattern generating ability are shown.