ベネット圧縮
Bennettのpebble gameでメモリと時間のトレードオフを体感する
背景： Bennett (1989) は n ステップの計算を k 個のpebble (= 中間値を保存できる枠) で可逆実行できることを示した。前進ステップは隣の空きマスにpebbleを置き、後退ステップは置いてあるpebbleを消す。目標： 最終ステップ n にpebbleを到達させ、それ以外を全て消去 (ガベージなし)。
ステージ: 1/6
段数 n: 3
上限 k: 2
使用中: 0
手数: 0
最良: --
操作
クリック マスにpebbleを置く / 取る UNDO 1手戻す HINT 次に押すべきマスを点滅 RESET ステージ最初から
各ステップ i のpebbleを操作する規則：
- step 0 (initial) は常にpebbleが置かれている (入力)。
- step i にpebbleを置けるのは step i-1 にpebbleがある場合のみ (forward step)。
- step i のpebbleを取れるのは step i-1 にpebbleがある場合のみ (reverse step)。
- 同時に置けるpebbleは k 個まで。step 0 は数えない。
Y Lab tieup: Bennett 1989の可逆チューリング機械の時空トレードオフを直接シミュレート。横山研の可逆計算理論 (R-WHILE/Janus等) で、不可逆プログラムを最小ガベージで可逆化する基本テクニック。