algorithm - Grossman & Zeitman のアルゴリズムを理解する

Question

Grossman & Zeitman が発行した論文「本質的に反復的なアッカーマン関数の計算」を読みました。この論文では、アッカーマン関数を最適化するアルゴリズムが提示されています。

アッカーマン関数が部分列 A(m,n) で結果を生成することはわかっています。

m=0: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,...
m=1: 2, 3, 4 , 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,...
m=2: 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33,...
m=3: 5, 13, 29, 61, 125, 253, 509, 1021, 2045, 4093, 8189, 16381, 32765 、65533、...
m=4: 13、65533、...

Next配列は、各サブシーケンスのどこにいるかを追跡し、Goal配列は、計算されたばかりの値を次のサブシーケンスに転送する前に到達する必要がある場所を追跡することであると述べられています。そして、それが行うのは、値に 1 をインクリメントすることだけです。

Ackermann(m, n)
    {next and goal are arrays indexed from 0 to m, initialized so that next[0] 
     through next[m] are 0, goal[0] through goal[m - l] are 1, and goal[m] is -1} 
    repeat
        value ← next[0] + 1 
        transferring ← true 
        current ← 0 
        while transferring do begin
           if next[current] = goal[current] then goal[current] ← value
                                            else transferring ← false
           next[current] ← next[current] + 1
           current ← current + 1 
           end while
    until next[m] = n + 1 
    return value {the value of A(m, n)}
    end Ackermann

2 つの配列が現在地/移動先をどのように示しているのか理解するのが難しいと思いますか? で停止したときの正確な意味を正確に特定するのに苦労していnext[m] = n + 1ます。なぜ具体的にこの値なのですか? アルゴリズムをトレースしてみましたが、どのように機能するのかまだわかりません。このアルゴリズムはボトムアップの実装としてカウントされますか?

これは、値、現在、および両方の配列を出力する Java コードです。

import java.util.Arrays;

public class Ack {
    static int arrayAck(int m, int n) {
        //Next array to keep track of where we are in each subsequence, 
        //and Goal array to keep track of where we need to reach before transferring the value just calculated to the next subsequence.
        int[] next = new int[m+1];
        int[] goal = new int [m+1];
        Arrays.fill(next, 0);
        Arrays.fill(goal, 1);
        goal[m] = -1;
        
        int value = next[0] + 1;
        while(true) {
            value = next[0] + 1;
            boolean transferring = true;
            int current = 0;
            
            System.out.println("--");
            System.out.println("Next = " + Arrays.toString(next));
            System.out.println("Goal = " + Arrays.toString(goal));
            System.out.println("Current= " + current);
            System.out.println("Value = " + value);
            while(transferring) {
                if(next[current] == goal[current])
                    goal[current] = value;
                else
                    transferring = false;
                next[current]=next[current]+1;
                current += 1;
                System.out.println("Current= " + current);
                System.out.println("Next = " + Arrays.toString(next));
                System.out.println("Goal = " + Arrays.toString(goal));
            }
            
            if(next[m]==n+1)
                break;
            
        }
        
        return value;
    }
     
    public static void main(String[] args) {
        int m=2,n=2;
        System.out.println("Ackermann value for ("+m+","+n+") = " + arrayAck(m, n));
    }

}