可逆計算、亜群、分断圏

• 参考："From reversible to irreversible computations" by Green, Altenkirch（http://www.mscs.dal.ca/~selinger/qpl2006/PDFS/05-Green-Altenkirch.pdf あるいは http://sneezy.cs.nott.ac.uk/qml/pub/GreenAlten06/GA06qpl.pdf）

可逆計算（reversible computations）のモデルは、亜群となる。亜群が骨格的、つまり、同型の対象は等しいとき、それは分断圏となる。よって、骨格的亜群は実質的に群の離散的な集まりに過ぎない。しかし、モノイド構造を持つ。

対称モノイド亜群にトレースを持たせることができる（こともある）。このトレースで繰り返し計算を行えるだろうか？もしできれば、トレース付き圏（対称モノイド圏）の枠組みで可逆計算もモデル化できる。

不可逆計算は、f:X→X を可逆計算として、X=A+H、X=B+G という分解を使って、(f, A, B)として定義できる。ここで、Hは初期化してないヒープ、Gは捨て去るゴミを意味している。X=A+Y+H、X=B+Y+Gとして、f:(A+H)+Y → (B+G)+Y としてからYでトレースを取ることで普通のトレースは実現できるのだろうか？