14
$\begingroup$

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?

$\endgroup$

2 Answers 2

24
$\begingroup$

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.

$\endgroup$
6
  • 4
    $\begingroup$ Further, using this technique one can simulate two stacks and that allows one to simulate a tape of a Turing Machine: to move right or left, we simply pop on one stack and push to the other, effectively storing on the stacks what's on the left/right side of the head. Similarly, one can also simulate arrays having one "cursor/iterator". (Of course, this is not very efficient as written above in the answer.) $\endgroup$
    – chi
    Commented Feb 28, 2023 at 14:17
  • 14
    $\begingroup$ Of course, the caveat about absolutely astronomical integers is kind of superfluous in a question about the Ackermann function! A recursive implementation in any normal programming language fares hardly better than this Gödel-WHILE one. $\endgroup$ Commented Feb 28, 2023 at 15:09
  • 3
    $\begingroup$ If anyone was nerd sniped by the neat formula: the way that works is that you are summing to a an offset which is the "area" (=number of points) inside the right triangle of the numbers you have already counted. The neat trick is that a + b + 1 is constant when you move diagonally on the line(s) x = -y + something that are used to exlore NxN, and gives you the side of the right triangle that you have already explored. $\endgroup$ Commented Feb 28, 2023 at 16:05
  • 2
    $\begingroup$ @VladimirCravero yes, or one might just mention that this is the Cantor pairing function. $\endgroup$ Commented Feb 28, 2023 at 16:49
  • $\begingroup$ Oh well, it's nice it has a name. I spent some time figuring things out without knowing that :) $\endgroup$ Commented Mar 1, 2023 at 10:48
3
$\begingroup$

Note: this answer assumes one more rule on the WHILE language (which is not in the paper linked by OP), which is that the variables within are limited to a certain size. It does not matter which size, but they are bounded by some arbitrary number (which could even be specific for each program, and itself arbitrarily large, but still a fixed upper bound). If you specifically wish to allow for the "encode/decode" answer posted elsewhere, then one should reasonably expect a similar addendum to the language to the opposite effect, i.e. allowing arbitrarily large numbers. In my opinion, this is an omission in the language definition, mostly irrelevant, but not for this question.

The WHILE statement as described in the paper linked by OP has these features:

It is a simple imperative language, with assignment to local variables, if statements, while loops, and simple integer and boolean expressions

Specifically, it has neither memory storage nor stack nor recursion nor any other unbounded feature. Each program in the WHILE language is of fixed size, with a fixed amount of variables, and no way to be dynamic in this regard.

(N.B. it is unclear to me why they mention "local" variables - the language has no functions, and thus no scopes, and thus no differentiation between local and global would make much sense.)

While another answer suggests to use the fact that the language does not bound the size of individual variables, and thus is able to store unlimited storage in a single variable, I will provide the opposite answer, assuming that the intention of the language is not to have this feature.

The language is clearly a constructed language to explore implications of such a basic set of features. The paper, as usual for these kinds of theoretical languages, does not care about the size or boundedness of its variables, but the spirit of the wording ("simple imperative language", "simple integer and boolean expressions") and the fact that they do not even analyze the language itself, but an assembly-like version WHILE3ADDRESS instead, makes quite clear that the intention behind the language is not to have infinitely sized variables as a cop-out to achieve Turing-completeness.

So for me, the fact that the paper does not mention a bound on the size of the individual variables, having unbounded variables would transform the language from "simple" to completely unsimple. As it stands now, this language is clearly meant to be one step below Turing-completeness (i.e., it is designed to have all features of Turing-completeness except for recursion and storage).

As such, the language, as it stands now, represents an excessively simple language without RAM, with a fixed (and thus bounded) amount of variables. It is not Turing-complete, since that would require unlimited recursion or unlimited memory.

The Ackermann function needs unbounded storage or recursion, and thus cannot be calculated by the WHILE function.

To look at only the subject of the question ("Ackermann Function without Recursion or Stack"), the answer is also "no" if there is also no other unbounded amount of storage (i.e., no RAM and no infinitely-sized integers).

$\endgroup$
3
  • 1
    $\begingroup$ The phrases "Turing-complete" and "can be calculated by" are very precise terms with precise definitions; you can't just invert the meaning of them to the opposite because it was not the "intention" of the language. I do understand your point, but you could simply define a version of the WHILE language with fixed-width integers and your argument would be clearer. $\endgroup$ Commented Mar 1, 2023 at 16:39
  • $\begingroup$ @CalebStanford, fair enough. I have added a cursive blurb at the beginning, I hope it's now clear. $\endgroup$
    – AnoE
    Commented Mar 1, 2023 at 19:53
  • $\begingroup$ yes, much better! :) Thanks for updating. $\endgroup$ Commented Mar 1, 2023 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.