Ackermann Function without Recursion or Stack

I have been studying the necessity of a WHILE loop when defining the Ackermann Function.
I am looking to write a program to compute the Ackermann function in a high level language such as Python or JavaScript to compare it to the WHILE language.

The Ackermann function is defined recursively, and recursive calls do not exist in the WHILE language.

Every program with an alternative method to recursion has used a stack. Stacks do not exist in the WHILE language. Is there any way to program the Ackermann function in a HLL without a stack or recursion?

Good question! It is possible using only natural numbers and arithmetic to implement a stack, due to Gödel numbering.

What's the basic idea? Well, a stack is basically a nested sequence of pairs: the stack $(1, 2, 3)$ (with $1$ on top) can be thought of as $(1, (2, 3))$. And in turn, we can encode pairs using this neat formula:
$$
\texttt{encode}(a, b) = a + \binom{a + b + 1}{2} = a + \frac{(a + b + 1)(a + b)}{2}
$$
This is called a pairing function and this one is due to Cantor.
Some examples may make the function more clear:
$$
\texttt{encode}(0, 0) = 0 + 0 = 0\\
\texttt{encode}(0, 1) = 0 + 1 = 1 \\
\texttt{encode}(1, 0) = 1 + 1 = 2 \\
\texttt{encode}(0, 2) = 0 + 3 = 3 \\
\texttt{encode}(1, 1) = 1 + 3 = 4 \\
\texttt{encode}(2, 0) = 2 + 3 = 5 \\
\texttt{encode}(0, 3) = 0 + 6 = 6 \\
\cdots
$$

Then we can also define a corresponding function $\texttt{decode}(n)$ which returns a pair of integers, so that $\texttt{decode}(\texttt{encode}(a, b)) = (a, b)$.
The kicker is that both encode and decode are definable as WHILE programs!
Implementing encode and decode

It should be clear how to implement $\texttt{encode}$: WHILE programs have arithmetic, so we can simply compute the answer in a single assignment statement. For $\texttt{decode}$, there are some more efficient ways, but one way that works is simply to loop over all pairs integers and try encoding them:

decode(n):
  a := 0
  b := 0
  done := 0
  while done == 0:
    c := encode(a, b)
    if c == n:
      done := 1
    else if a > 0:
      a := a - 1
      b := b + 1
    else:
      a := b + 1
      b := 0

The line c := encode(a, b) is a subprocedure: it can be simply replaced inline with the definition of encode.
Implementing a stack

What operations does a stack data type need to support? There are basically just four operations: empty: S returning an empty stack; push: (S, nat) -> S pushing a new value; pop: S -> (S, nat) popping the top value, and is_empty: S -> bool to check whether the stack is empty. Each of these can be implemented using encode and decode. For the empty stack, we can use the natural number 0. For push, we can use

push(stack, n) = encode(stack, n) + 1

and for pop, we can use:

pop(stack) = if stack == 0 then (0, 0) else decode(stack - 1)

where the return value, an ordered pair, is stored into two designated variables.
Finally, is_empty is just checking whether stack == 0.
Implementing Ackermann

As you noted, recursive functions can be implemented using WHILE loops and a stack. So implementing the Ackermann function is just a matter of applying the stack implementation above. Each time you want to push or pop from the stack, you replace with the above procedures. You can have as many stacks as you want, stored in different natural number variables.

The same trick works to implement any recursive or Turing-computable function; this is why WHILE is Turing-complete.
Notes

Finally, two caveats. First, none of these encodings are particularly efficient. Even the basic encode function is quite unwieldy; nested calls to it to create a stack creates absolutely astronomical integers very quickly.

Second, for any of this to work, it's important that the natural numbers in the WHILE language are true integers, not the fixed-width integers that are common in real computer architectures. For fixed-width integers, the WHILE language is certainly weaker than arbitrary computation -- it cannot implement any nontrivial Turing-computable functions, let alone the Ackermann function.

As a result of both of these limitations, in practice, WHILE is not really sufficient for general computation with recursive functions. Instead, real compilers rely on the program stack and dynamically allocated memory on the heap to implement complex data structures and computations.

StackExchange Computer Science Q#157790, answer score: 24