Asset Details
Do you wish to reserve the book?
A Difference in Complexity Between Recursion and Tail Recursion
Hey, we have placed the reservation for you!
By the way, why not check out events that you can attend while you pick your title.
Oops! Something went wrong.
Looks like we were not able to place the reservation. Kindly try again later.
Are you sure you want to remove the book from the shelf?
A Difference in Complexity Between Recursion and Tail Recursion
Do you wish to request the book?
A Difference in Complexity Between Recursion and Tail Recursion
Please be aware that the book you have requested cannot be checked out. If you would like to checkout this book, you can reserve another copy
We have requested the book for you!
Your request is successful and it will be processed during the Library working hours. Please check the status of your request in My Requests.
Oops! Something went wrong.
Looks like we were not able to place your request. Kindly try again later.
Journal Article
A Difference in Complexity Between Recursion and Tail Recursion
2017
Overview
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
]).
Publisher
Springer US,Springer Nature B.V
Subject
