# How can any non-primitive-recursive function like the Ackermann function be implemented on hardware?

If for-loops and function calls both boil down to jump instructions when implemented on a real machine, then how is "The Ackermann function isn't implementable with for-loops" a meaningful phrase?

• Function calls don't boil down to (just) jump instructions. Also, without context "The Ackermann function isn't implementable with for-loops" isn't very meaningful. – Derek Elkins left SE Sep 16 '19 at 4:31

Real machines have access to a stack, and so can implement recursion. This is all that is needed to implement the Ackermann function.

However, the Ackermann function grows very fast, so you would only be able to calculate a few of its values given realistic time and space constraints.

The phrase "The Ackermann function isn't implementable with for-loops" is shorthand for "The Ackermann function $$A(m,n)$$ cannot be implemented using bounded for-loops where an upper bound on the number of iterations in each loop is determined in advance from the values of the parameters $$m$$ and $$n$$". In other words the Ackermann function is not primitive recursive.

The Ackermann function can, of course, be implemented using while-loops (where a bound on the number of loop iterations is not fixed in advance). And while-loops can be reduced to simple logical tests and conditional jump instructions (this is what a compiler does).

Another way of expressing this is to say that the Ackermann function can be implemented in FlooP but not in Bloop.

I have an answer by demonstration; here's what x86-64 gcc 4.8.5 has to say on the issue. Here's the C code:

int ackermann(int m, int n) {
if (m == 0) {
return n + 1;
}
else if (m > 0 && n == 0) {
return ackermann(m - 1, 1);
}
else if (m > 0 && n > 0) {
return ackermann(m - 1, ackermann(m, n - 1));
}
return 1;
}
int main() {
return 0;
}


And here's the assembly output:

ackermann:
pushq   %rbp
movq    %rsp, %rbp
subq    $16, %rsp movl %edi, -4(%rbp) movl %esi, -8(%rbp) cmpl$0, -4(%rbp)
jne     .L2
movl    -8(%rbp), %eax
addl    $1, %eax jmp .L3 .L2: cmpl$0, -4(%rbp)
jle     .L4
cmpl    $0, -8(%rbp) jne .L4 movl -4(%rbp), %eax subl$1, %eax
movl    $1, %esi movl %eax, %edi call ackermann jmp .L3 .L4: cmpl$0, -4(%rbp)
jle     .L5
cmpl    $0, -8(%rbp) jle .L5 movl -8(%rbp), %eax leal -1(%rax), %edx movl -4(%rbp), %eax movl %edx, %esi movl %eax, %edi call ackermann movl -4(%rbp), %edx subl$1, %edx
movl    %eax, %esi
movl    %edx, %edi
call    ackermann
jmp     .L3
.L5:
movl    $1, %eax .L3: leave ret main: pushq %rbp movq %rsp, %rbp movl$0, %eax
popq    %rbp
ret


A for-loop only compiles to a jump instruction; however, the instructions movl %eax, %esi, movl %edx, %edi, and call ackermann are relevant here. A call may behave like a jump, but it include the movement of parameters too, which a simple jump doesn't have.