this function just recurses, decrementing num_levels until it hits zero, and chasing the parent pointers. With that, I have random access all over the stack.
Of course, C is ultimately a finite state machine because pointers have a fixed width. "sizeof pointer" is a constant expression. The absolute number of objects which can be addressed is finite. In an abstract program which doesn't use sizeof on pointers or work with their internal representation in any way, we can relax this model to allow an unlimited space; we just understand that we can have as many stack frames as we want and that somehow, the & operator in any one of them produces unique pointers.
> Of course, C is ultimately a finite state machine because pointers have a fixed width.
Yes, but I'm willing to let that slide as long as you never do anything with a pointer but dereference one or compare two of them to see if they're equal (because you have to assume that to make any interesting computational model Turing-complete). But I'm not willing to let num_levels slide. If num_levels has a fixed width (and in C it would have to unless you show me how to build a purely functional bignum library) this solution won't work.
It really is not trivial to figure out how to make this work.
Of course, C is ultimately a finite state machine because pointers have a fixed width. "sizeof pointer" is a constant expression. The absolute number of objects which can be addressed is finite. In an abstract program which doesn't use sizeof on pointers or work with their internal representation in any way, we can relax this model to allow an unlimited space; we just understand that we can have as many stack frames as we want and that somehow, the & operator in any one of them produces unique pointers.