×

General design of reversible sequential machines based on reversible logic elements. (English) Zbl 1304.68126

Summary: This paper proposes a scheme for decomposing reversible sequential machines (RSMs) into simple reversible logic elements (RLEs). This scheme is generalized from the previous constructions of reversible Turing machines (RTMs) using various RLEs [J. Lee et al., ibid. 460, 78–88 (2012; Zbl 1279.68081)], in which each RTM is composed by a uniform circuit of identical RSMs associated with two states. Each RSM’s operation in the circuit, however, is subject to strict conditions that prevent direct extension of their constructions to more general RSMs. Our novel scheme to the contrary, imposes no condition on the operations of an RSM which may take any arbitrary number of states. Moreover, each RSM’s construction can work asynchronously without a clock signal to synchronize all RLEs comprising the construction.

MSC:

68Q45 Formal languages and automata
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)

Citations:

Zbl 1279.68081
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Fredkin, E.; Toffoli, T., Conservative logic, Internat. J. Theoret. Phys., 21, 3-4, 219-253 (1982) · Zbl 0496.94015
[2] Gupta, P.; Agrawal, A.; Jha, N. K., An algorithm for synthesis of reversible logic circuits, IEEE Trans. CAD, 25, 11, 2317-2330 (2006)
[3] Hauck, S., Asynchronous design methodologies: an overview, Proc. IEEE, 83, 1, 69-93 (1995)
[4] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Massachusetts · Zbl 0426.68001
[5] Lee, J.; Peper, F.; Adachi, S.; Morita, K.; Mashiko, S., Reversible computation in asynchronous cellular automata, (UMC2002. UMC2002, LNCS, vol. 2509 (2003)), 220-229 · Zbl 1029.68101
[6] Lee, J.; Peper, F.; Adachi, S.; Morita, K., An asynchronous cellular automaton implementing 2-state 2-input 2-output reversed-twin reversible elements, (ACRI 2008. ACRI 2008, LNCS, vol. 5191 (2008)), 67-76 · Zbl 1159.68497
[7] Lee, J.; Yang, R. L.; Morita, K., Design of 1-tape 2-symbol reversible Turing machines based on reversible logic elements, Theoret. Comput. Sci., 460, 78-88 (2012) · Zbl 1279.68081
[8] Lee, J.; Adachi, S.; Xia, Y. N.; Zhu, Q. S., Emergence of universal global behavior from reversible local transitions in asynchronous systems, Inform. Sci., 282, 38-56 (2014) · Zbl 1355.68092
[9] Morita, K.; Shirasaki, A.; Gono, Y., A 1-tape 2-symbol reversible Turing machine, Trans. IEICE, 72, 3, 223-228 (1989)
[10] Morita, K., A simple universal logic element and cellular automata for reversible computing, (Proc. 3rd Int. Conference on Machines, Computations, and Universality. Proc. 3rd Int. Conference on Machines, Computations, and Universality, Chisinau. Proc. 3rd Int. Conference on Machines, Computations, and Universality. Proc. 3rd Int. Conference on Machines, Computations, and Universality, Chisinau, LNCS, vol. 2055 (2001)), 102-113 · Zbl 0984.68512
[11] Morita, K., Reversible computing and cellular automata — a survey, Theoret. Comput. Sci., 395, 1, 101-131 (2008) · Zbl 1145.68036
[12] Ogiro, T.; Kanno, A.; Tanaka, K.; Kato, H.; Morita, K., Nondegenerate 2-state 3-symbol reversible logic elements are all universal, Int. J. Unconv. Comput., 1, 47-67 (2005)
[13] Sahoo, R. R.; Rath, G. S., Designing a cryptosystem by implementing reversible sequential switching M/C — a symmetric approach, Int. J. Comput. Commun. Technol., 2, 173-175 (2010)
[14] Toffoli, T., Reversible computing, (de Bakker, J. W.; van Leeuwen, J., Automata, Languages and Programming. Automata, Languages and Programming, LNCS, vol. 85 (1980)), 632-644
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.