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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.