「可逆計算が面白いから、JavaScriptで書いてみた」とか言ってみたわけですが、どこが面白いのでしょう。まー、面白いってのは個人的な感覚だから説明しにくいのですが、オシャベリとしてなにやら書いてみます。
僕は、環境問題やエネルギー問題の知識はろくにないし、「熱心なエコロジスト」なんてことはまったくありません。が、やっぱりリソース（資源）とかエネルギーは気になる、なんとなく。
僕がよく使う機械といえばコンピュータ。クーラーや冷蔵庫だけじゃなくて、コンピュータだって電気使って熱を吐き出します。なんか後ろめたい。現実のこの機械のことじゃなくて原理的なハナシでも、計算するとリソースとエネルギーを使うらしいです。計算つっても、結局は物理過程だから外部環境を汚してしまうんですよね。
ランダウアー（Landauer）の原理によると、情報を消去すると必然的に外部環境のエントロピーを上げてしまうそうです（よくわかっとらん、受け売り）。これは計量的な法則で、1ビットの情報を消すと、最低でも kβ×(log 2) （kβはボルツマン定数）のエントロピー上昇を招く、と（よくわかっとらん、受け売り）。中間段階で蓄積した情報を捨てるような計算では、必ず環境を汚すことになります。
ただしこれは、情報を捨ててしまう計算のときです。完全に情報を保持する計算なら、エネルギー消費も環境への影響もなく計算ができる可能性があります。それが可逆計算なんです。可逆計算では、「入力が与えられる → 計算を実行する → 結果を出力する」という過程を、映画フィルムを逆回しするように逆転させられます。つまり、出力（結果）から入力を再現できます。別な言い方をすると、時間に明白な方向性がなく、過去と未来の区別はつきません。
グリーンとアルテンキルヒの論文だと、可逆計算から非可逆計算を作るときに、ヒープとゴミという概念が使われています。ヒープは、入力ではないが、最初にセットアップすべきメモリです。ゴミは、計算途中で使われたかも知れないが、結果を取り出すときには忘れられるメモリです。ヒープのセットアップ（例えばゼロクリア）で以前の情報が失われ、ゴミは捨ててしまう（永久に使われないかもしれない、再利用では初期化のコストがかかる）のでこれも情報が失われます。
逆説的に聞こえますが、すべてを憶えておくためにリソースやエネルギーが必要なのではなくて、不要なことを忘れるためにリソースやエネルギーが使われるようです。忘れたこと／捨てたことは戻ってきません。よって、過程を逆転することはできなくなり、過去という概念が生まれのでしょう（いやっ、よく分からんけど）。
さてところで、可逆計算は十分な計算能力を有するのでしょうか？ フレドキン（Fredkin）ゲートのような可逆ゲートの組み合わせで、非可逆計算をシミュレートできます。ベースとなる可逆計算（可逆回路）に対して、その一部をヒープとゴミに割り当てれば、どんな非可逆計算でも作れるのです。そういう意味では、可逆計算の計算能力は十分です。
我々は非可逆計算（例えば足し算や論理AND）に慣らされているので、可逆計算によるアルゴリズムをイメージしにくいのですが、ヒープやゴミをできるでけ減らしたアルゴリズムを考えることは、ひょっとして北極グマを救うことにつながるのかも知れません。
関連するエントリー：
