機密情報をインターネットなどで送受信するとき、送信者はデータを「暗号」にして、受信者はそれを「復号」して内容が理解できる平文に戻します。このように互いに逆になる計算には、データの圧縮・伸張やワープロソフトの「元に戻す」などがあります。
もしソフトに不具合があると大変です。受信者は暗号データを平文に戻せません。では、ソフトの正しさの保証は可能なのでしょうか。残念ながら、一般的にこの問題を解決する方法はありません。
最近、私が興味があるのは、どの操作も必ず元に戻せる計算です。こういった可逆な計算を巧く記述するための言語と方法論について研究をしています。
ひとつ原理を流れ図で示します。左下図は、2通りの方法でxとyの和と差を求めています。図の上側の流れ図では右側の値から左側の値が求まらない（非可逆）のに対して、図の下側の流れ図（可逆）では求まります。例えば、可逆な流れ図で暗号器を設計すると、逆から値を入力すると必ず正しい復号器にもなります。
|
