Fredkin gates in simple reversible cellular automata. Issue 3 (4th May 2022)

• Record Type: Journal Article
• Authors: Morita, Kenichi
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 37:Issue 3(2022)
• Page Start: 249
• Page End: 272
• Publication Date: 2022-05-04
• Subjects: Fredkin gate -- reversible logic gate -- reversible computing -- reversible cellular automaton -- elementary triangular partitioned cellular automaton; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2022.2052871
• Languages: English
• ISSNs: 1744-5760

Abstract

Abstract : In this paper, we give a survey on the problem of how a Fredkin gate, a universal reversible logic gate, is realised in various reversible cellular automata (RCAs). Models of RCAs considered here are two kinds of square partitioned cellular automata (SPCAs), and four kinds of elementary triangular partitioned cellular automata (ETPCAs). These six RCAs are very simple, in particular, ETPCAs are extremely simple, yet they are computationally universal in the sense any reversible Turing machine, which is composed of Fredkin gates, can be embedded in them. There are three key points for implementing a Fredkin gate in an RCA: (1) realising a signal, (2) routeing a signal, and (3) interacting two signals. We shall see that depending on the properties of the RCAs, different techniques are used to realise the above three functions. Based on these techniques, complete configurations of Fredkin gates in the six RCAs are given.