A rotary element (RE) is a typical reversible logic element with one-bit memory. It has four input lines and four output lines, and its operation is very easily understood. Despite its simplicity, any reversible Turing machine (RTM) can be constructed only of it in a systematic way. In this paper, we give implementation methods of an RE in very simple two-dimensional reversible cellular automata. The model considered here is an elementary square partitioned cellular automaton (ESPCA). A square cell of ESPCA consists of four parts each of which has two states, and thus it is a 16-state CA. A local function of ESPCA is described by six local transition rules. Here, we consider three reversible ESPCAs. We show that, in each of these ESPCAs, an RE is constructed utilizing only a few kinds of small patterns and their interactions. Once an RE is implemented, any RTM is embedded in its cellular space more easily than to use only reversible logic gates. Full computing processes of RTMs in these ESPCAs can be viewed using a general purpose CA simulator Golly.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Composing a Rotary Element in Simple Reversible Cellular Automata to Make Reversible Computers

  • Kenichi Morita

摘要

A rotary element (RE) is a typical reversible logic element with one-bit memory. It has four input lines and four output lines, and its operation is very easily understood. Despite its simplicity, any reversible Turing machine (RTM) can be constructed only of it in a systematic way. In this paper, we give implementation methods of an RE in very simple two-dimensional reversible cellular automata. The model considered here is an elementary square partitioned cellular automaton (ESPCA). A square cell of ESPCA consists of four parts each of which has two states, and thus it is a 16-state CA. A local function of ESPCA is described by six local transition rules. Here, we consider three reversible ESPCAs. We show that, in each of these ESPCAs, an RE is constructed utilizing only a few kinds of small patterns and their interactions. Once an RE is implemented, any RTM is embedded in its cellular space more easily than to use only reversible logic gates. Full computing processes of RTMs in these ESPCAs can be viewed using a general purpose CA simulator Golly.