読者です 読者をやめる 読者になる 読者になる

アッカーマン操作

VBA

今読んでいる本 『コンピュータは数学者になれるのか? 数学基礎論から証明とプログラムの理論へ (照井一成)』の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

qiita.com