可逆計算

可逆計算（かぎゃくけいさん、英: Reversible computing）とは、可逆な、すなわち計算過程において常に直前と直後の状態が一意に定まる計算。可逆計算は、計算過程において情報が消失しないため非破壊的計算（Non-destructive computing）としても知られている。

例

• 可逆ハードウェア
  • 量子計算
• 可逆論理ゲート
  • NOTゲート
  • 制御NOT（CN）ゲート
  • トフォリゲート（CCNゲート）
  • フレドキンゲート
  • ビリヤードボール・コンピュータ
• 可逆計算模型
  • 遷移函数が一対一である決定的チューリングマシンは可逆的である（可逆チューリングマシン）。
  • 可逆セル・オートマトン
• 可逆命令セットアーキテクチャ
  • Pendulum
• 可逆プログラミング言語
  • Janus
  • Conservation
• 可逆難解プログラミング言語
  • 難解プログラミング言語には実行する計算そのものは単純なものも多いため、可逆になるように修正するのが簡単なものもある。#外部リンク参照。
• 可逆アプリケーションソフトウェア
  • エディタ（テキストエディタに限らず、ペイントソフトなども含む）の編集操作を、ドキュメントを状態 d₁ から状態 d₂ に変化させる関数 e(d₁) → d₂ だと見れば、アンドゥ（Undo）機能のあるエディタにおけるその操作の undo は e^-1(d₂) → d₁ という逆関数とみなすことができ、全体として見て一種の可逆計算になっている（ただし、この場合は正確にはドキュメント本体以外に、アプリケーションが内部で持っている undo のための情報も関数の引数に含める必要がある）。
  • エンコーダとデコーダ: 通常、データをエンコードするエンコーダ、エンコードされたデータを元に戻すデコーダはそれぞれ別々に実装するが、非可逆圧縮などでなければ、可逆プログラミング言語で実装すると、エンコーダを逆に動かせばデコーダになる。

歴史

可逆計算、特にその原理とハードウェアに対する初期の興味は、計算のために必要なエネルギーはどれくらいか？ という計算理論と物理学が重なった問題と繋がっている。スーパーコンピュータから電卓まで、さらにはそろばんの珠を動かすのに必要なエネルギーまで、計算のためには何らかの最低限必要なエネルギーというものがありそうに現実的には思える。

しかし、チャールズ・ベネットが明らかにしたところでは、フォン・ノイマン＝ランダウアーの限界に従ってエネルギーが消費されるのは、情報が失われる時であると結論された（マクスウェルの悪魔も参照）。このことから、可逆計算はエネルギーを消費することなく（正確には、必要なだけゆっくりと過程を進めることにより、いくらでも少ないエネルギーで）行うことができる。

もちろん、現実の物理法則に従って、どうやればそのようなコンピュータを作ることができるか、は別の問題であり、我々が現在使っているパーソナルコンピュータや携帯情報端末の消費電力を、明日にでもどうこうできる、といったものではないし、ランダウアーの限界は我々が通常使っている集積回路の動作するエネルギーとは桁が違うものだが、理論では以上のように示されている。

近年の可逆計算に対する興味は、検証など様々な分野からのものがあるが、そのうちの一つに量子計算が挙げられる。量子計算は量子過程によって計算を行うものであり、量子物理学の法則は時間について可逆である。そのため、量子系にさせる計算に関して、そのモデルは可逆でなければならない。

参考文献

• ファインマン, R. P. 著, ヘイ, A., アレン, R. 編, 原康夫他訳 (1999) 『ファインマン計算機科学』 岩波書店, ISBN 4-00-005941-6, 第5章 「可逆計算と計算の熱力学」.
• 森田憲一『可逆計算』（計算モデルが中心）

外部リンク

• MicroPower: Towards Low-Power Microprocessors with Reversible Computing 計算の全てのレイヤを可逆にする、という「fundamental challenge」について、最後に述べられている。「Tower of reversible computing system」という概念を示すものとして言及されることがある。
• Design of Reversible Computing Systems Logic, Languages, and Circuits (PDF)
• http://esolangs.org/wiki/Category:Reversible_computing Esolang（難解言語Wiki）の可逆計算カテゴリ