数理解析研究所講究録
第 1799 巻 2012 年 167-170

167

記憶付き可逆論理素子の能力の階層構造について
向井 優太 *, 森田 憲一 **広島大学大学院工学研究科
概要

可逆コンピュータを構成するための基本素子として記憶付き可逆論理素子が研究されている．

特に，素子の能力の重要な指標である万能性について多くの研究が行われている．任意の記憶付$k>2$ について全ての非縮き可逆論理素子をシミュレートできることを万能という．これまで，

退 2 状態 記号可逆論理素子が万能であること，そして一部の非縮退 3 状態 2 記号可逆論理素子が万能であることが示されていた．したがって，万能な 2 状態 2 記号可逆論理素子が存在するか否かが大きな課題となっている．本稿では，2 状態 2 記号可逆論理素子 4 つの内，3 つの素子が非万能であることを示した．またこの結果は，記憶付き可逆論理素子の能力に真の階層構造が存$k$在することも意味している．

1

はじめに

ここで可逆論理素子は，その動作関数が単射であり，したがって現在の状態と出力から，1 時刻前の状態と入力

なわち可逆論理ゲートの研究は Toffoli [6, 7], およびRedkin, Tofffoli [2] により物理的可逆性との関連で研究され，Tofffoli ゲート [6] と Fredkin ゲート [2] が共をもとに， :$\delta_{1}$$Q\cross\Sigmaarrow Q,$$\forall p,q\in Q,\forall s\in\Sigma,\forall t\in\Gamma$が一意に決定できる性質を持った素子である (ただし可逆論理ゲートの場合は状態の概念がない). 可逆論理素子には，記憶機能を持つものと持たないものの 2 種類が考えられる．記憶機能を持たないもの，す$\delta$$\delta_{2}$:$Q\cross\Sigmaarrow$を次のように定める．

$\Gamma$:

ffl $\delta(p,s)=(q,t)$$\delta_{1}(p,s)=q\wedge\delta_{2}(p,s)=t$$\delta_{1},\delta_{2},$$Q,$$\delta$を次のように拡張したものを$\delta_{2}^{*}:Q\cross\Sigma^{*}arrow\Gamma^{*},$$\delta_{1}^{*}:Q\cross\Sigma^{*}arrow$$\delta^{*}:Q\cross\Sigma^{*}arrow Q\cross\Gamma^{*}$とする．
$\forall q\in Q,\forall s\in\Sigma,$ $\forall\sigma\in\Sigma^{*}$に論理万能であることが示された．他方，Morita[3]により，1 ビットの記憶を持つ可逆論理素子の一種

$=$

$q$

$\delta_{1}^{*}(q, \sigma s)$$=$$\delta_{1}(\delta_{1}^{*}(q, \sigma), s)$$\delta_{2}^{*}(q,\epsilon)$$=$$\epsilon$$\delta_{2}^{*}(q, \sigma s)$$=$$\delta_{2}^{*}(q, \sigma)\cdot\delta_{2}(\delta_{1}^{*}(q, \sigma), s)$$\delta^{*}(q, \sigma)$$=$$(\delta_{1}^{*}(q, \sigma), \delta_{2}^{*}(q, \sigma))$であるロータリー素子が提案され，この素子を用いて可逆チューリングマシンを構成できることが示された．また，この構成では信号を同期させる必要がなく，可逆論理ゲートによるものより単純に実現で:$\delta_{1}^{*}(q,\epsilon)$

きる．

ロータリー素子は，2 つの状態と 4 つの入出力を持つ 2 状態 4 記号記憶付き可逆論理素子の一種である．任意の記憶付き可逆論理素子について，その素子をシミュレートする回路を構成できるような素子$k>2$ について全てを万能であると呼ぶ．これまで，以下では，上記のように拡張した
めて$\delta_{1},$$\delta_{2},$$\delta$$\delta_{1}^{*},$$\delta_{2}^{*},$$\delta^{*}$

をあらたと書く．

記憶付き可逆論理素子は，可逆有限状態機械の個々の入出力記号についてそれぞれ対応する入出力線を持つような論理素子とする．可逆有限状態機械 $M=$に対応する素子は，状態 $q\in Q$ のとき$\delta(q, s)=$に対応する入力線から信号を受けると，して一部の非縮退 3 状態 2 記号素子が万能であるこ$(t,p)$ のとき，状態に対応する出力線に遷移してとが示されている [8]. したがって，2 状態 2 記号素子に万能なものが存在するか否かが大きな課題であ へ信号を送り出す動作を行う．以降は，$M$ を単に記憶る．本稿では，非縮退 2 状態 2 記号素子 4 つのうち， 付き可逆論理素子と呼ぶ．また，本稿ではの非縮退 2 状態$k$

記号素子が万能であること [4], そ$S\in$$(Q, \Sigma, \Gamma, \delta)$$\Sigma$$t$$p$$|\Sigma|=|\Gamma|$

2-2-2, 2-2-3 および 2-2-4 の 3 つの素子が非万能であることを示す．

であるような素子を対象とする．すなわち入出力線数はそれぞれであり，これを記号数と呼ぶ．
状態 $m$ 記号素子 $M=(Q, \Sigma, \Gamma, \delta)$ は，$Q=$$|\Sigma|$$n$$\{q_{1}, \ldots, q_{n}\},$

2$\Sigma=\{s_{1}, \ldots, s_{m}\},$に固定したとき， を準備$\delta$$\delta(q_{n}, s_{m}))$$\Gamma=\{t_{1}, \ldots, t_{m}\}$$(\delta(q_{1}, s_{1}),$$\delta(q_{1}, s_{2})$, . . .,という列で表現できるため，これを辞書定義 1 有限状態機械 $M$ を次のように定義する． 順に並べたときの番号 を用いてその素子を 状態$M=(Q, \Sigma, \Gamma, \delta)$ , ただし$n-m-k$ と表記する． 状態
は状態の有限集合， $m$ 記号 番素子と呼び，
$k$

$Q$

及び$\Gamma$$k$$\Sigma$はそれぞれ入力記号，出力記号の有限集合，

$m$

$n$

$n$

記号素子は， 番から $(|Q|\cross|\Sigma|)!-1$ 番まで存在$0$:
は写像であり遷移関数と呼ぶ． する．
記憶付き可逆論理素子は状態数と記号数が比較的
また， が単射であるとき $M$ を可逆有限状態機械と呼ぶ．
小さいものでも多数存在する．しかし，その中には$\delta$$Q\cross\Sigmaarrow Q\cross\Gamma$$\delta$168
記号名や状態名を付け替えるだけで同じ素子になるようなものが存在し，それらは等価であるとみなせる．そのため，等価な素子の集合からそれぞれ最も番号の小さなものを選んで代表素子と呼び，以降は代表素子のみを扱う．さらに，より少ない状態数あるいは記号数の素子と同じ動作を行う素子が存在する．そのような素子を縮退していると呼ぶ．縮退素子は，その形式上の状態数，記号数を持つ素子として扱う必要がなく，考察の対象から外してよい．
2 状態 2 記号可逆論理素子のうち非縮退で代表のものは，2-2-2, 2-2-3, 2-2-4 および 2-2-17 の 4 つである [5]. これらの素子を表す $M_{2-2-2},$ $M_{2-2-3},$ $M_{2-k4}$
および$M_{2arrow 2-17}$を次のように定義する．

$M_{2-2-2}=(\{q_{0},q_{1}\},\{a,b\},\{x,y\},\delta^{2-2-2})$,$\delta^{2-2-2}=\{((q_{1},a),(q_{0},y)),((q_{1},b),(q_{1},y))((q0,a),(q_{0},x)),((q_{0},b),(q_{1},x)),$$M_{2-2-3}=(\{q_{0},q_{1}\},\{a,b\},\{x,y\},\delta^{2-2-3})$力である．次に，回路への入力は直前の入力に対する出力が得られた後に与えるものとする．すなわち回路中の信号の数を高々1 と制限する．したがって，信号の同期を考慮する必要がなく，信号の速度も任意でよい．これらの制約のもとでも，任意の可逆チュー
リングマシン [1] をロータリー素子と呼ばれる素子
2-4-289 のみを用いた回路でシミュレートできることがわかっている [3].
上記の制約を満たすように記憶付き可逆論理素子の回路を次のように定義する．回路 $C$ は，$=$$=$個の記憶付き可逆論理素子
それぞれ個の回路の入出$m$,
カポート $I=\{i_{1}, \ldots, i_{m}\},$ $O=\{0_{1}, \ldots, 0_{m}\}$ , 及び接続 $E$ ,$(Q_{i}, \Sigma_{i}, \Gamma_{l}, \delta^{:}))_{1\leq i\leq n}$$E:I \cup(\bigcup_{i=1}^{n}\{i\}\cross\Gamma_{i})\Rightarrow O\cup(\bigcup_{1=1}^{n}\{i\}\cross\Sigma_{1})$

$\}$

,$\}$

$b$$E$いることを意味する．可逆論理回路においては，,$E(a)=b$ のときを全単射に制限する．したがって，$\delta^{2-2-4}=\{((q_{1},a),(q_{0},y)),((q_{1},b),(q_{1},a))((q0,a),(q_{0},x)),((q_{0},b),(q_{1},y)),$$M_{2-2-17}=(\{q0,q_{1}\}, \{a,b\},\{x,y\},\delta^{2-2-17})$$t\in\Gamma_{i}$$M_{i}$$a$$M_{2-2-4}=(\{q_{0},q_{1}\},\{a,b\},\{x,y\},\delta^{2-2-4})$,$(i, s)$ はの 4 組 $C=(M_{1ist}, I, O, E)$ で表す．ただし，に$(i, t)$ はの出力の入力 $s\in$ 昂に，はとが接続されて$E(a)=b$それぞれ対応し，$M_{i}$$\delta^{2-2-3}=\{((q_{1},a),(q_{1},y)),((q_{1},b),(q_{0},y))((q_{0},a),(q_{0},x)),((q_{0},b),(q_{1},x)),$$(M_{i}$$M_{1ist}$$n$$E^{-1}(b)=a$ である．

$\}$

また，ある回路の入出力とある素子の入出力を対応付け，任意の入力列に対してそれら 2 つの出力列が等しいとき，その回路，もしくは回路を構成する素,$\delta^{2-2-17}=\{((q_{1},a), (q_{0},y)),((q_{1},b),(q0,x))((q0,a),(q_{1},x)),((q_{0},b),(q_{1},y)),$$\}$子の集合はその素子をシミュレートするという．あまた，これらの素子は図 1 のように表現できる．例え$\delta^{2-2-2}(q0, a)=(q_{0},x)$ば 2-2-2 の場合，は，図中のと書かれた側の$a$の矢印と$x$$q0$の矢印を繋ぐ点線に対応する．このように，四角の中に書かれた矢印を繋ぐ線はその状態毎の入力と出力の対応を，すなわちる素子，あるいは素子の集合について，任意に与えられた記憶付き可逆論理素子に対してその素子をシミュレートする回路を構成できるとき，その素子，あるいは素子の集合を万能であるという．

信号の進み方を示している．信号が点線を通る場合

3は素子の状態は変化せず，実線を通る場合はもう一方の状態に遷移する．以上のようにすることで，こ示す．の表記によって素子を一意に表すことができる．

非万能な記憶付き可逆論理素子
2-2-2, 2-2-3 および 2-2-4 が非万能であることを定理 22-2-2 は，2-2-3, 2-2-4 および 2-2-17 をシミュレートできない．

証明

任意に与えられた， 個の 2-2-2 を用いた回路, ただし, について，その頂点集合$n$$C=((M_{1}, \ldots, M_{n}), \{i_{1},i_{2}\}, \{0_{1},0_{2}\}, E)$$\ovalbox{\tt\small REJECT}=M_{2-2-2}$$V= \{i_{1}, i_{2},0_{1},0_{2}\}\cup(\bigcup_{\dot{l}=1}^{n}\{i\}\cross\{a, b\})\cup(\bigcup_{\dot{l}=1}^{n}\{i\}\cross\{x, y\})$

図 1:2 状態 2 記号可逆論理素子の非縮退代表素子 [5].

を次を満たすように巧と巧に分割できる．

本稿では，記憶付き可逆論理素子の回路を次の 2つの制約を満たすように構成したものとする．まず，回路中の任意の接続線は，ある素子のある入力とある素子のある出力を一対一で接続する．これにより，回路中の信号の数が増減することはなく，可逆性に$i_{1}\in V_{1}$.

$\forall v\in\{i_{1},i_{2}\}\cup(\bigcup_{=1}^{n}\{i\}\cross\{x,y\})$$[v\in V_{1}\Leftrightarrow E(v)\in V_{1}]$.

$(i,a)\in V_{1}\Leftrightarrow(i,x)\in V_{1}$

加えて保存性も満たす．回路中の素子の接続されて$(i, b)\in V_{1}\Leftrightarrow(i, y)\in V_{1}$いない入力と出力は，それぞれその回路の入力と出$V_{2}=V-V_{1}$

.

.

.

169になること，そして防と巧への所属について，01 と 02 で異なることは容易に確認できる．01と 02 について， に属するものを , そして に$i_{2}\in V_{2}$$V_{1}$

属するものを$0_{2}’$

2-2-3, 2-2-4 および 2-2-17 はそれぞれ次のような動作が可能である．

$V_{2}$$0_{1}’$と置く．次に，$i\in\{1, \ldots n\}$を，$\delta_{2}^{2-k3}$$M_{i}$の入出力の頂点 $(i,a),$ $(i, b),$ $(i,x),$ $(i, y)$ が全て$V_{1}$$\delta_{2}^{2-2-4}$に属するもの，全て巧に属するもの，そして防とへの所属が分かれるものの 3 種類に分割する．それぞれ，,$A_{2}=\{i\in\{1, \ldots, n\}|(i, a)\in V_{2}\wedge(i, x)\in V_{2}\}$ ,$\cdots$$q_{0},$$\cdots$$q_{0},$$\delta_{2}^{2-2-17}$$V_{2}$$A_{1}=\{i\in\{1, \ldots, n\}|(i, a)\in V_{1}\wedge(i,x)\in V_{1}\}$bbbbbb ) $=xyxyxy\cdots$ .
( bababa ) $=yyyyyy\cdots$ .
( bbbbbb ) $=xyxyxy\cdots$ .
($\cdots$$q_{0},$

このような動作は，これらの素子の入出力と $C$ の入出力 il,をどのように対応付けても， からという入出力の回数と からという入出力の$i_{2},0_{1}’,0_{2}’$$i_{1}$$o_{2}’$$0_{1}’$$i_{2}$

回数の差を任意に大きくできる．したがって，2-宴 2

では 2-2-3, 2-2-4 および 2-2-17 をシミュレートでき$A_{3}=\{i\in\{1, \ldots, n\}-A_{1}-A_{2}$ない

口とする．以上を図示すると図 2 のようになる．

定理 32-2-3 は，2-2-4 および 2-2-17 をシミュレートできない．

証明$n$個の 2-2-3 による回路 $C$$=$$((M_{1}, \ldots, M_{n})$,, ただし $M_{i}=M_{2-2-3}$ , が 22-4 をシミュレートすると仮定する．ここで，2-2-4 すととなわちとの入出力は， と$\{0_{x}, 0_{y}\},$$\{i_{a}, i_{b}\},$$C$$M_{2-2-4}$$o_{x},$

図 2: 2-2-2 回路の分割．

$O$と$0_{y}$.

.
.に属する素子でのみ信号は巧から巧へ，もしくは巧から巧へ移動できる．
$A_{3}$に属する素子について，ある状態の時はから巧への移動と$\delta_{2}^{2arrow 2-4}$から($q_{0},$bababo$b$$i_{b},$$X$$V_{1}$$V_{2}$$\cdots$

回路 $C$ の状態は回路中の$n$) $=yyyyyy\cdots$ .

個の 2-2-3 の状態の組でのに対応する回路の状表すことができる．
態を 1 つ選び，その回路の状態を $qc$ と置く．このときある が存在し，状態の回路に対して，ibia を$M_{2-2-4}$$k$$V_{1}$への移動のみが可能で，もう一方の状態の時は から砺への$V_{2}$$i_{a},$がそれぞれ対応するものとする．また以がいえる．
$A_{3}$$a$降の議論は 2-2-4 を 2-2-17 に置き換えても成立する．
$M_{2-2-4}$ は次のような動作ができる．

以上の分割方法と 2-2-2 の遷移関数より次のこと

.

$E)$

$q_{0}$$q_{C}$

回繰り返した入力列を与えると回路の状態が $qc$ に戻る．そのような が存在しないことは回路の可逆$k$$k$移動と巧から巧への移動のみが可能である．

性に反する．またこの時の出力列は，回路が 2-2-4 を間を信号がに属する素子について，移動したときかつそのときに限り，その素子ののである．この $2k$ 回の入出力の動作について，回路の頂点集合 $V=V_{1}\cup V_{2}$ , ただし$A_{3}$$V_{1},$$V_{2}$

状態はもう一方へ遷移する．
信号力 il からへ移動するとき，その間に信号が巧から巧へ移動する回数は巧からシミュレートする仮定より$i_{y}$

を $2k$ 回繰り返したも$V_{1}= \{i_{a},i_{b}\}\cup(\bigcup_{i=1}^{n}\{i\}\cross\{x,y\})$$\grave\grave\grave$,$0_{2}’$$V_{2}= \{0_{x},0_{y}\}\cup(\bigcup_{i=1}^{n}\{i\}\cross\{a,b\})$$V_{1}$

へ移動する回数より丁度 1 回多い．

以上より，il から という入出力の度に， に属する素子の内巧から へ移動できる状態の素子が丁$A_{3}$$0_{2}’$,のうち，信号が一度も通っていない頂点 $V’\subset V$ に注目する．次が成立するのは明らかである．

$V_{2}$

度 1 つ減り， から$V_{2}$$V_{1}$へ移動できるような素子が丁度 1 つ増えることがいえる． から$i_{2}$$0_{1}’$という入出力についても，同様に上記と反対のことがいえる．
したがって， は有限であるため，回路 の動作は，$C$$A_{3}$$i_{1}$

から$0_{2}’$という入出力の回数と$i_{2}$から$0_{1}’$という入出力の回数の差が有限でなくてはならない．

$\forall v_{1}\in V_{1}[v_{1}\in V’\Leftrightarrow E^{-1}(v_{1})]$.

$|V’\cap V_{1}|=|V’\cap V_{2}|$ であることがいえ
これより，$0_{x}\in V’$ であるため，る．明らかに$i_{a},$ $i_{b},$$0_{y}\not\in V’,$の頂点の中では $|V’\cap V_{2}|$ に属するものが $|V’\cap V_{1}|$ に属するものより 1 つ多くなっている．したがって，あるについて，$\{i_{a},i_{b},0_{x}, 0_{y}\}$$M_{i}$$|\{(i, x), (i, y)\}\cap V’|>|\{(i, a), (i, b)\}\cap V’|$

170
2-2-17$V’$ への所属を満たさなければならない．すなわち，について， 側が 側より多くなければならない．
$V_{1}$$V_{2}$$|\{(i,x), (i, y)\}\cap V’|=2\wedge|\{(i, a), (i, b)\}\cap V’|<2$の場合，素子に入力された信号が消滅することになるため，$|\{(i,x), (i, y)\}\cap V’|=1\wedge|\{(i, a), (i, b)\}\cap V’|=0$が成立する．の遷移関数より， に が入力されたときは必ず状態がもう一方に変わり，かつ状態が変わる$M_{12-3}$のは$b$$M_{1}$$b$$|\{(i, a), (i, b)\}\cap$に入力された時のみである．

$V’|=0$ より $(i, b)\not\in V’$ となるため，$M_{i}$は少なくとも 1 度は状態が変わっている．さらに，回路の状態が元に戻っているという仮定より， は 2 回以上のを入力されていることがいえる．ここで，入力列に が 2 回以上含まれるとき，その出力列にと が必ず両方現れることは容易に確認できる．したがって，$M_{2-2-3}$

$b$

$x$

$y$

$(i, b)\not\in V’\Rightarrow(i, x)\not\in V’\wedge(i,y)\not\in V’$$|\{(i, x), (i, y)\}\cap V’|=1$に矛盾する．

以上より， が 2-2-4 あるいは 2-2-17 をシミュレートすると仮定すると矛盾が導かれ，したがって 2-2-3$C$は 2-2-4 および 2-2-17 をシミュレートできない．口定理 42-2-4 は，2-2-3 および 2-2-17 をシミュレートできない．

証明は，2-2-3 と 2-2-4 が入出力について鏡像のような関係になることを用いると定理 3 と同様の方法でできるため省略する．

2-2-3, 2-2-4 および 2-2-17 は 2-2-2 をシミュレートすることができる [8]. この結果と定理 2,3,4 を合わせると，全ての非縮退 2 状態 2 記号素子の階層構
造は図 3 のようになる．

4

まとめ

2-2-2, 2-2-3 および 2-2-4 それぞれについてシミュレートできない素子が存在することを証明し，これらの素子が非万能であることを示した．これは，記憶付き可逆論理素子に真の階層構造が存在することも意味している．また，2-2-3, 2-2-4 が 2-2-2 をシミュレートすることはできるが，2-2-2 が 2-2-3, 2-2-4 をシミュレートすることはできないため，非万能な素子の間にも能力差が存在することがわかる．2 状態
3 記号素子および 3 状態 2 記号素子からは万能なものが見つかっているため，これらより状態数や記号数が少ない素子の中で万能である可能性のあるもの
は 2-2-17 のみとなり，これが未解決問題として残されている．

$Aarrow B$ は造．

$A$が $B$ をシミュレートできることを，$Aarrow B$ は $A$ が $B$をシミュレートできないことをそれぞれ示す．

$b$$M_{1}$である．しかしこれは，

図 3: 非縮退 2 状態 2 記号可逆論理素子の階層構

参考文献[1] C. H. Bennett. (1973). Logical reversibility ofcomputation. $IBM$ J. Res. Dev., 17:525-532.
[2] E. Fredkin and T. Toffoli. (1982). Conservativelogic. Int. J.
. Phys., 21:219-253.
$?7\iota eoret$[3] K. Morita. (2001). A simple reversible logic element and cellular automata for reversible computing. In Proc. 3rd Int. Conf. on Machines,Computations, and Universality, LNCS 2055,pages 102-113. Springer-Verlag.
[4] K. Morita, T. Ogiro, A. Alhazov, andT. Tanizawa. (2012). Non-degenerate 2-state
reversible logic elements with three or more
symbols are all universal. J. Multiple-Valued
Logic and Soft Computing, 18:37-54.

[5] K. Morita, T. Ogiro, K. Tanaa, and H. Kato.
(2005). Classification and universality of reversible logic elements with one.bit memory. InProc. 4th Int. Conf. on Machines, Computations, and Universality, LNCS 3354, pages 245256. Springer-Verlag.
[6] T. Toffoli. (1980). Reversible computing. In
Automata, Languages and Progmmming, LNCS
85, pages 632-644. Springer-Verlag.

[7] T. Toffoli. (1981). Bicontinuous extensions ofinvertible combinatorial functions. Mathematical Systems Theory, 14:12-23.
[8] 向井優太，森田憲一．(2011). 2 記号記憶付き可逆論理素子の万能性．In 2011 年度夏の LA シンポジウム予稿，pages S $16-1-S16-15$ .