Talk:Reduction (computability theory)
Add topic| This is the talk page for discussing improvements to the Reduction (computability theory) article. This is not a forum for general discussion of the subject of the article. |
Article policies
|
| Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
 | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
"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)
The first sentence of a Wikipedia article should define the subject, using a declarative "Subject is X-Y-Z" style.
This is not currently the case. The article reads:
In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied.
This is not a definition. It tells me (an amateur, not a mathematician) nothing whatsoever about the subject matter.
The first sentence should read something like:
In computability theory, reduction is ...
Or perhaps:
In computability theory, reducibility is ...
I leave this for someone else; I don't have the knowledge to do it right.