| 題名 | 2 記号記憶付き可逆論理素子の万能性 |
| 著者 | *向井 優太, 森田 憲一, 岩本 宙造, 今井 克暢 (広島大学大学院工学研究科) |
| Page | pp. 103 - 104 |
| Keyword | 可逆コンピューティング, 記憶付き可逆論理素子, 計算万能性 |
| Abstract | 計算機の更なる小型化のためには，可逆性を満たした計算を用いる必要がある．そのような可逆計算機の基本素子として，記憶付き可逆論理素子が研究されている．これまで，全ての2状態k記号記憶付き可逆論理素子(k>2)が万能であること，そして2状態2記号の3番素子と4番素子の組み合わせが万能であることが知られていた．本研究では，計算機による探索で6つの万能な3状態2記号素子を発見し，2記号の万能素子が存在することを明らかにした．さらに，2状態2記号の3番素子と17番素子，および4番素子と17番素子の組み合わせが万能であることを発見した． |
| 題名 | サイクリックタグシステムの適切な符号化による3記号万能可逆チューリングマシンの小サイズ化 |
| 著者 | *池田 隼人, 森田 憲一, 岩本 宙造, 今井 克暢 (広島大学大学院工学研究科) |
| Page | pp. 105 - 106 |
| Keyword | チューリングマシン, 可逆, サイクリックタグシステム |
| Abstract | 論理素子の更なる小型化の鍵になると考えられている可逆コンピューティングといういものがある。本研究では可逆コンピューティングのモデルの中でも最も基本的な可逆チューリングマシンを題材とし、特に小サイズの3記号の万能可逆チューリングマシンを構築する研究を行なった。 本研究では万能性を実現するために任意のサイクリックタグシステムを媒介として模倣することによって、間接的に万能性を持たせる方法を採用した。 このサイクリックタグシステムに関して適切な符号化を行うことにより、昨年度発表したものから最小状態数を33状態減らし3記号49状態の万能可逆チューリングマシンを構築した。 |
| 題名 | 一般化シャノアール問題のNP困難性 |
| 著者 | *角田 佑輔, 岩本 宙造, 森田 憲一, 今井 克暢 (広島大学大学院工学研究科情報工学専攻) |
| Page | pp. 107 - 108 |
| Keyword | シャノアール, 無向グラフ, NP困難, ネコ, 捕獲者 |
| Abstract | シャノアールゲームとは捕獲者がネコを逃さないように追い詰めるゲームである。このゲームは１つのマスが６つのマスに隣接するボード上で行う。捕獲者は一手でマスを１つ除去し、ネコは一手で除去されていないマスに移動する。捕獲者はネコの逃走可能な経路を全て断つことが出来ればゲームに勝利する。本研究ではボードを任意の一般化された無向グラフに置き換えた一般化シャノアール問題について考える。一般化シャノアール問題ではグラフ上でネコが予めk個の頂点を除去するという条件を付けて行う。本稿ではネコが捕獲者にどこに追い込まれてもゴールに辿りつくことが可能となるk個の頂点の選び方が存在するかという問題がNP困難であることを示す。 |
| 題名 | ストリングパズルの計算複雑さ |
| 著者 | *佐々木 健斗 (広島大学大学院工学研究科情報工学専攻), 岩本 宙造, 森田 憲一, 今井 克暢 (広島大学大学院工学研究科) |
| Page | pp. 109 - 110 |
| Keyword | 計算複雑さ, ストリングパズル |
| Abstract | 本研究では, 分解パズルの一つであるストリングパズルを扱う. 分解パズルとは, 複数の機械的に連結したピースからある一つのピースを取り外すことを目的とするパズルである. 本研究では, 一般化ストリングパズル問題について考える. 一般化ストリングパズル問題の入力は, 一つのボードと複数のひもの初期状態の配置図である. 本研究では, 任意の論理式fからなるSATからストリングパズルへの多項式時間還元が存在し, fが充足可能であるとき, かつそのときに限り, ストリングパズルが解けることを示した. この結果から, 一般化ストリングパズル問題はNP困難である. |
| 題名 | 記憶付き可逆論理素子と可逆論理ゲートの分類 |
| 著者 | *伊吹 拓也, 森田 憲一, 岩本 宙造, 今井 克暢 (広島大学大学院工学研究科) |
| Page | pp. 111 - 112 |
| Keyword | 可逆コンピューティング, 記憶付き可逆論理素子, 可逆論理ゲート, 論理万能性 |
| Abstract | 可逆論理素子は現在の出力と状態から直前の入力と状態を唯一に決定できる論理素子であり、素子の微細化や発熱エネルギーの低減化などの面で注目されている。本研究では複数の状態を持つ可逆論理素子を「記憶付き可逆論理素子」、1つしか状態を持たない素子を「可逆論理ゲート」と呼んで区別し、それぞれについて研究した。特にこれまで未解明であった2状態5記号可逆論理素子と2入力2, 3, 4, 5出力および3入力3出力可逆論理ゲートのそれぞれに対して同値類と呼ばれる本質的に等価な能力を持った素子を導出し, 分類を行った。将来、記憶付き可逆論理素子および可逆論理ゲートが可逆コンピューティングの発展に寄与することが期待される。 |
| 題名 | チューリングマシンを直接模倣する可逆セルオートマトン |
| 著者 | *長岡 勇介, 森田 憲一, 岩本 宙造, 今井 克暢 (広島大学大学院工学研究科) |
| Page | pp. 113 - 114 |
| Keyword | 可逆セルオートマトン, 計算万能性, チューリングマシン |
| Abstract | 可逆セルオートマトン(RCA)は格子状に配置された単純なセルと規則からなる可逆計算モデルである．RCAは微視的な物理現象をモデル化した枠組みとして見ることができ，その計算能力の研究が盛んに行われている．計算能力，特に計算万能性は基本的な計算モデルである任意のチューリングマシン(TM)や他の計算万能なモデルを模倣することで示される．過去の研究では，小型で計算万能なRCAが構築されているが，計算時間は考慮されていなかった．本稿では，TMを直接的に模倣することで計算時間の点で優れた計算万能なRCAの構築法を示す． |