I&C Journal 2016 Journal Article
Regressive computations characterize logarithmic space
- Stefano Mazzanti
We consider the function class E generated by the constant functions, the projection functions, the predecessor function, the substitution operator and the recursion on notation operator. Furthermore, we introduce regressive register machines, which have division by 2 and the predecessor on natural numbers as basic operations. We show that E is the class of functions computable by regressive machines and that the sharply bounded functions (functions with logarithmic size values) of E coincide with the sharply bounded logspace computable functions.