Regressive computations characterize logarithmic space

详细信息    查看全文

• 作者：Stefano Mazzanti ^{mazzanti@iuav.it" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Logspace computable function ; Recursion on notation ; Regressive machine
• 刊名：Information and Computation
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：251
• 期：Complete
• 页码：16-35
• 全文大小：470 K

文摘

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.