Lecerf複号

Lecerf-Bennettトリックで非可逆計算を可逆化する練習場

背景： 非可逆な関数 y = f(x) を可逆化する古典的手法。
1. forward (履歴付): (x, _) → (x, y, hist) — 入力を保存しつつ計算履歴を残す。
2. copy: (x, y, hist, _) → (x, y, hist, y) — 結果を XOR で別レジスタへコピー。
3. uncompute: (x, y, hist, y) → (x, _, _, y) — 履歴を逆走して中間状態を消去。
残るのは入力 x と結果 y のみ — ガベージなし。これがLecerf 1963 / Bennett 1973 の鍵。

STAGE: 1/4 関数: 2x x: 3 目標 y: 6 ステップ: 0/3 位相: forward

Lecerf-Bennett

矢印キー → で1ステップ進める、← で1ステップ戻す。
3位相 (forward → copy → uncompute) を完走し、ガベージ無しで結果を取り出せばクリア。

ヒント: copy 位相のときに矢印を押すと結果が出力レジスタに転送される。uncompute は forward と完全に逆。

操作

→ 1ステップ前進　← 1ステップ後退　SPACE 位相を進める (forward終了→copy→uncompute)　AUTO 自動実行　RESET 最初から

レジスタ：X=入力 (不変)、HIST=履歴スタック、Y=作業域 (再利用される)、OUT=結果 (XORでコピーされる)。完走時に X と OUT 以外が全て 0/空になることを確認。

Y Lab tieup: Lecerf 1963の可逆化定理 — 任意のチューリング機械を可逆化できることを示した。横山研の可逆計算理論で、Janus/R-WHILEの「不可逆プログラムをガベージなしで可逆化」する基本テクニックそのもの。

Lecerf複号

Lecerf-Bennett

CLEAR

操作