Talk:Reduction (recursion theory)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Low Priority
 Field: Foundations, logic, and set theory

"Bounded reducibilities"[edit]

This article uses "bounded reducibility" to refer to a reduction which has a finite constant bound on the number of oracle queries. Soare (at least in his forthcoming book) uses "bounded Turing" to mean a Turing reduction with computably bounded use - i.e., synonymously with wtt reduction. A Google search returns, in addition to this article, some complexity theory papers talking about specific computable use bounds (eg polytime), one reference to a constant number of queries bound, and a few references to computably bounded use. Any proposed resolutions to the collision? skeptical scientist (talk) 14:30, 10 June 2007 (UTC)