Regressive computations characterize logarithmic space

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.

Authors

• Stefano Mazzanti

Keywords

• Logspace computable function
• Recursion on notation
• Regressive machine