可逆計算

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

可逆性

この目的のために特に重要な、密接に関連する2つの主要な可逆性のタイプがある。それは、物理的可逆性と論理的可逆性である。あるプロセスが物理的に可逆であると言われるのは、それが物理的エントロピーの増加をもたらさない場合である。これは等エントロピーであることを意味する。この特性を理想的に示す回路設計のスタイルは、チャージリカバリ論理、断熱回路、または断熱計算と呼ばれる（断熱過程を参照）。実際には、どんな非定常な物理プロセスも完全に物理的に可逆または等エントロピーにすることはできないが、システムの進化を記述する物理法則が正確に知られており、未知の外部環境との相互作用から十分に隔離されたシステムでは、完全な可逆性にどこまで近づくことができるかの限界は知られていない。可逆計算を実現する技術の研究の動機の一つは、それがコンピュータの計算エネルギー効率（つまり、消費される単位エネルギーあたりに行われる有用な演算）を、不可逆ビット演算ごとに散逸するkT ln(2)のエネルギーというフォン・ノイマン＝ランダウアー限界を超えて向上させる唯一の潜在的な方法であると予測されていることである。ランダウアー限界は2000年代のコンピュータのエネルギー消費量の何百万分の一、2010年代のコンピュータのエネルギー消費量の何千分の一であったにもかかわらず、可逆計算の支持者は、これが実際の回路設計においてランダウアー限界の影響を大きく拡大するアーキテクチャ上のオーバーヘッドによるものが大きく、可逆計算の原理を使用しない限り、実用的な技術が現在のエネルギー効率レベルを大幅に超えることは困難である可能性があると主張している。

例

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

歴史

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

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

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

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

熱力学との関係

IBMで働いていたロルフ・ランダウアーが最初に主張したように、計算過程が物理的に可逆的であるためには、論理的にも可逆でなければならない。ランダウアーの原理とは、nビットの既知の情報を忘却的に消去するためには、熱力学的エントロピーにおいて常にnkT ln(2)のコストが発生するという見解である。離散的で決定論的な計算過程は、古い計算状態を新しい計算状態にマップする遷移関数が 1 対 1 の関数である場合、すなわち、出力論理状態が計算演算の入力論理状態を一意に決定する場合、論理的に可逆的であるという。

非決定論的(確率的またはランダム的であるという意味で)の計算過程の場合、古い状態と新しい状態の間の関係は一価関数ではなく、物理的可逆性を得るために必要な条件は、わずかに弱い条件、すなわち、計算が進むにつれて、可能な初期計算状態の特定のアンサンブルのサイズが平均して減少しないという条件になる。

参考文献

• ファインマン, 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）の可逆計算カテゴリ