An instruction set for reversible Turing machines

摘要

A reversible Turing machine (RTM) is a standard model of reversible computing that reflects physical reversibility. So far, to describe an RTM the quadruple formulation and the quintuple formulation have been used. In this paper, we propose the program form as a new formulation for RTMs. There, an RTM is described by a sequence of only five kinds of instructions. It is shown that any RTM in the quintuple form is converted to an RTM in the program form, and vice versa. We also show each instruction is implemented by a particular reversible logic element with memory called a rotary element (RE) very simply. Hence, a circuit that simulates a given RTM is easily and systematically constructed out of REs.