On the convergence of query-bounded computations and logical closure properties of C.e. Sets
Journal of Symbolic Logic 66 (4):1543-1560 (2001)
| Abstract | Call a set A n-correctable if every set Turing reducible to A via a Turing machine that on any input makes at most n queries is Turing reducible to A via a Turing machine that on any input makes at most n-queries and on any input halts no matter what answers are given to its queries. We show that if a c.e. set A is n-correctable for some n ≥ 2, then it is n-correctable for all n. We show that this is the optimal such result by constructing a c.e. set that is 1-correctable but not 2-correctable. The former result is obtained by examining the logical closure properties of c.e. sets that are 2-correctable | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,709 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesMichael Huemer (2005). Logical Properties of Warrant. Philosophical Studies 122 (2):171 - 182.
Wolfgang Merkle & Nenad Mihailović (2004). On the Construction of Effectively Random Sets. Journal of Symbolic Logic 69 (3):862-878.
Richard Beigel, William Gasarch, Martin Kummer, Georgia Martin, Timothy McNicholl & Frank Stephan (2000). The Complexity of Oddan. Journal of Symbolic Logic 65 (1):1 - 18.
Yaroslav Sergeyev & Alfredo Garro (2010). Observability of Turing Machines: A Refinement of the Theory of Computation. Informatica 21 (3):425–454.
William I. Gasarch, Mark G. Pleszkoch & Robert Solovay (1992). Learning Via Queries in $\Lbrack +, < \Rbrack$. Journal of Symbolic Logic 57 (1):53 - 81.
Verónica Becher, Santiago Figueira, Serge Grigorieff & Joseph S. Miller (2006). Randomness and Halting Probabilities. Journal of Symbolic Logic 71 (4):1411 - 1430.
Jack Copeland (1999). Beyond the Universal Turing Machine. Australasian Journal of Philosophy 77 (1):46-67.
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan & Leen Torenvliet (2006). Enumerations of the Kolmogorov Function. Journal of Symbolic Logic 71 (2):501 - 528.
Timothy H. McNicholl (2000). On the Commutativity of Jumps. Journal of Symbolic Logic 65 (4):1725-1748.
Michael Benedikt & H. Jerome Keisler (2003). Definability with a Predicate for a Semi-Linear Set. Journal of Symbolic Logic 68 (1):319-351.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
