Scholz posed in 1952 the problem of characterising the class of spectra (of formulas in first-order logic with equality), and there soon after came interesting related questions by Asser, Bennett, Mostowski, etc. In the early 1970s Alan Selman and I discovered an exact characterisation of spectra.

The problem interested me because of its similarity to the “LBA problem” then widely studied in theoretical computer science. Spectra had properties very similar to the context-sensitive languages, and I began with the hypothesis that they were the same class. The correct answer turned out to be different, that spectra equal NEXPTIME. This result was in a way a product of its time, since this characterisation of “the spectrum problem” would not have been naturally expressible prior to the the development in the late 1960s by Hartmanis, Stearns and others of time- and space-bounded complexity classes.

Since then a wide range of research has been done in finite model theory, datalog, programming languages and “implicit complexity”, to name a few closely related topics. From my computer science background a natural next question was: what is the expressive power of various subrecursive programming languages on finite input data structures? This brings up questions of the effects of imposing limits on both stored data, and on control structures. The talk will conclude with an array of results (many obtained by others), point out some regularities, and a tantalising fact (in my opinion) that is still not satisfactorily understood: that primitive recursion as a control structure seems to be inherently less expressive than general recursion or even tail recursion.