A Difference in Complexity Between Recursion and Tail Recursion

作者：Bhaskar Siddharth^*

来源：Theory of Computing Systems, 2017, 60(2): 299-313.

DOI：10.1007/s00224-016-9673-5

• Abstract recursion theory
• Tail recursion
• Lower bounds
• Arithmetic

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]).

• 出版日期2017-2