# Gurevich's theorem on primitive recursive functions being logspace-computable

I recently came across the following result attributed to Gurevich, according to which I understood that the class of problems solvable by primitive recursive functions is precisely the class L of problems computable in logarithmic space.

I attach a screenshot from Neil Immerman's book Descriptive Complexity, where I found the result.

Now, this seems very confusing to me, since it is known that the class PR is strictly bigger than L (see, for example, https://en.wikipedia.org/wiki/PR_(complexity) or https://math.stackexchange.com/questions/4170046/are-primitive-recursive-functions-computable-in-logarithmic-space). I imagine the theorem I attach is not talking about PR and L, but about something else. I'd appreciate some help in clarifying this.

• Logspace is the true logspace. But primitive recursive functions as defined here are much weaker than the usual class of primitive recursive functions, which would correspond to what you would get if A were the infinite structure N, whereas here we only consider finite structures. Aug 5 at 11:13