アッカーマン操作
今読んでいる本 『コンピュータは数学者になれるのか？ 数学基礎論から証明とプログラムの理論へ （照井一成）』の155ページに アッカーマン操作 というものが登場した。Ackermann関数の数列版みたいなものである。
非負整数の有限列<...>に対して次のような変換のパターンが定義されていて、列の長さが1になったら終わるというものだ。
{n, 0, ...} ----> {n + 1, ...}
{0, m +1, ...} ----> {1, m, ...}
{n + 1, m +1, ...} ----> {n, m + 1, m, ...}
{n} ----> end
この変換はVBAで簡単に定義できる。
Function Ackermann(ByRef a As Variant, ByRef dummy As Variant) As Variant Dim ret As Variant If sizeof(a) < 2 Then ' sizeof は VBAHaskell の関数 Ackermann = Empty ElseIf a(1) = 0 Then ret = tailN(a, sizeof(a) - 1) ' tailN は VBAHaskell の関数 ret(0) = a(0) + 1 swapVariant Ackermann, ret ' swapVariant は VBAHaskell の関数 ElseIf a(0) = 0 Then ret = a ret(0) = 1 ret(1) = a(1) - 1 swapVariant Ackermann, ret Else ret = cons(a(0) - 1, a) ' cons は VBAHaskell の関数 ret(1) = a(1) ret(2) = a(1) - 1 swapVariant Ackermann, ret End If End Function Function p_Ackermann(Optional ByRef firstParam As Variant, Optional ByRef secondParam As Variant) As Variant p_Ackermann = make_funPointer(AddressOf Ackermann, firstParam, secondParam) End Function
VBAHaskell の generate_while_not 関数は、初期値からスタートして条件が成り立つまでのあいだ、操作を繰り返して履歴を出力する。
<1, 3> からスタートしてみると、108 のステップで終了した。
' // <1, 3> から Empty になるまで Achermann 操作 （上限1000回） m = generate_while_not(VBA.Array(1,3), p_is_empty, p_Ackermann, 1000) ?sizeof(m) 108 for each z in m : printM z : next z 1 3 0 3 2 1 2 2 0 2 1 2 1 1 1 2 0 1 0 1 2 1 0 0 1 2 2 0 1 2 3 1 2 2 1 0 2 1 1 0 0 2 0 1 0 0 0 2 1 0 0 0 0 2 2 0 0 0 2 3 0 0 2 4 0 2 5 2 4 2 1 3 2 1 1 2 2 1 1 1 1 2 1 1 1 1 0 2 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 2 0 1 1 1 1 1 3 1 1 1 1 1 2 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 2 0 0 0 1 1 1 1 3 0 0 1 1 1 1 4 0 1 1 1 1 5 1 1 1 1 4 1 0 1 1 1 3 1 0 0 1 1 1 2 1 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 2 0 0 0 0 0 1 1 1 3 0 0 0 0 1 1 1 4 0 0 0 1 1 1 5 0 0 1 1 1 6 0 1 1 1 7 1 1 1 6 1 0 1 1 5 1 0 0 1 1 4 1 0 0 0 1 1 3 1 0 0 0 0 1 1 2 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 2 0 0 0 0 0 0 0 1 1 3 0 0 0 0 0 0 1 1 4 0 0 0 0 0 1 1 5 0 0 0 0 1 1 6 0 0 0 1 1 7 0 0 1 1 8 0 1 1 9 1 1 8 1 0 1 7 1 0 0 1 6 1 0 0 0 1 5 1 0 0 0 0 1 4 1 0 0 0 0 0 1 3 1 0 0 0 0 0 0 1 2 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 0 1 4 0 0 0 0 0 0 0 1 5 0 0 0 0 0 0 1 6 0 0 0 0 0 1 7 0 0 0 0 1 8 0 0 0 1 9 0 0 1 10 0 1 11 1 10 1 0 9 1 0 0 8 1 0 0 0 7 1 0 0 0 0 6 1 0 0 0 0 0 5 1 0 0 0 0 0 0 4 1 0 0 0 0 0 0 0 3 1 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 7 0 0 0 0 0 0 8 0 0 0 0 0 9 0 0 0 0 10 0 0 0 11 0 0 12 0 13
