A Difference in Complexity Between Recursion and Tail Recursion

详细信息    查看全文

• 作者：Siddharth Bhaskar
• 关键词：Abstract recursion theory ; Tail recursion ; Lower bounds ; Arithmetic
• 刊名：Theory of Computing Systems
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：60
• 期：2
• 页码：299-313
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation; Computational Mathematics and Numerical Analysis;
• 出版者：Springer US
• ISSN：1433-0490
• 卷排序：60

文摘

There are several ways to understand computability over first-order structures. We may admit functions given by arbitrary recursive definitions, or we may restrict ourselves to “iterative,” or tail recursive, functions computable by nothing more complicated than while loops. It is well known that in the classical case of recursion theory over the natural numbers, these two notions of computability coincide (though this is not true for all structures). We ask if there are structures over which recursion and tail recursion coincide in terms of computability, but in which a general recursive program may compute a certain function more efficiently than any tail recursion, according to some natural measure of complexity. We give a positive answer to this question, thus answering an open question in Lynch and Blum (Math. Syst. Theory. 12(1), 205-211 [5]).