Primitive recursive functions are syntactically constructible in the sense that from a set of "axioms" we can build every function in the set $PR$. This basicly means that we can build a machine that prints the definition for every function in $PR$.


Now, we can build hierarchies in the set $PR$ by adding some semantic restrictions. For example Grzegorczyk created hierarchy $\{\mathcal{E}\_i\}$ by restricting the rate of growth of the functions in each level.


I found papers mentioning the fact that if we take the second level of Grzegorczyk-hierarchy and define $E\_2 = \{ f\in\mathcal{E}\_2| ran(f)\in\{0,1\}\}$ (i.e. give yet another semantic restriction), then $E\_2$ encapsulates LINSPACE (to my understanding its not actually this straightforward, but the idea should come clear).


In this construction we started defining functions syntactically and added some semantic constraints to come up with a class of functions computable in linear space. 


This motivates to ask if there exists any constructions which provide ways to deploy purely syntactic machinery to produce, say, all the Turing-machines that run in polynomial space / time / whatever complexity class? Or functions instead of Turing-machines?


Is this even possible?



Syntactically capturing complexity classes
If you are interested in characterizations using recursion operators like in the definition of primitive recursive functions or the Grzegorczyk hierarchy, Cobham characterized P (or rather, FP, as a class of functions on binary strings) as the closure of a handful of initial functions under composition and limited recursion on notation: the latter allows to construct a new function $f$ on binary strings from functions $g,h\_0,h\_1,k$ by


$$\begin{align\*}f(\epsilon,\vec y)&=g(\vec y)\\f(x\smallfrown a,\vec y)&=\operatorname{Tr}(h\_a(x,\vec y,f(x,\vec y)),k(x,\vec y))\end{align\*}$$


where $\operatorname{Tr}(x,y)$ is string $x$ truncated to at most $|y|$ bits.


You can obtain PSPACE by modifying $E\_2$ so that you include among the initial functions some function of polynomial growth (in terms of bit length), such as $f(x)=2^{|x|^2}$. It is possible to give a characterization using some sort of recursion for classes like L, $NC^1$, or $AC^0[2]$, but it gets rather messy, and you usually need to throw in closure under $AC^0$-reductions, which rather spoils the picture.


