UCLA

There are several ways to understand computability over first-order structures. We may admit functions given by arbitrary recursive definitions, or we may restrict ourselves to “iterative” functions computable by nothing more complicated than while loops.

In the classical case of recursion over the natural numbers, these two notions of computability coincide. However, this is not true in general. We ask whether there is a model-theoretic classification of structures over which iteration is as powerful as recursion. We give such a classification for non-locally finite structures, and examine the problem of iteration versus recursion for the locally finite structures of finite fields and finite abelian groups. Over these structures, we prove that the question of iteration versus recursion reduces to a hard open problem in computational complexity theory.

We also ask whether there are structures in which certain function may be more efficiently computable by recursion than iteration, according to some measure of complexity. We identify a family of such structures with arbitrarily large gaps in efficiency.