多重再帰の打ち切り

今日：1 合計：925

多重再帰構文を, 数値関数で打ち切ることを考えましょう. 例えば

f(X,T):[1]X[2]f([3]f(sX,T-1),[4])

という関数定義ですね. 多重再帰が常に2段階読み込まれるように, さらに[3]を定数にしてみましょう.

f(X,T):[1]X[2]f([3]f(sX,T-1),10)

さて, この関数を適当な初項で実行することを考えます. すると,
全ての数値が1以上である間は, 数値のない多重再帰

f(X):[1]X[2]f([3]f(sX))

と同じように振る舞います. そこで, 数値0が現れる瞬間を観察しましょう.

f(X,1) = [1]X[2]f([3]f(sX,0),10) = [1]X[2]f([3],10)

数値が0になり, 多重再帰にならなくなった瞬間, 新たにf([3],10)という関数に突入することが分かります.
したがって, この構文は (特殊な初項のあと) 無限ループに突入することが分かります.

さて, より慎重に

f(X,T):[1]X[2]f([3]f(sX,T-1)[4],10)

という関数を見てみましょう. [4]は先ほどは付けていませんでしたが, ここではなるべく一般的に論じてみます.
すると

ということが分かります. 非常に非常に複雑でヤバイ構文なので,
どのくらい応用があるのか今でも未知数な部分もありますね.

特にすごいのは[3]の働きで,

という3つの役割を果たせています. つまり単純化した

f(X,T):Xf([1]f(sX,T-1),10)

という程度の構文でも, 不思議な短縮が可能となるのです. 試しに

f(X,T):Xf(lf(sX,T-1),10)
f(,1)

などというコードを実行してみてください.

180度回転および周期間の方向転換 (これは"l"が実行されないため起こる) などをしており,
到底コード中に"l"が1つしかないとは思えませんね！

問題例