David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 51 (2):273-291 (1986)
We give a new characterization of the hyperarithmetic sets: a set X of integers is recursive in e α if and only if there is a Turing machine which computes X and "halts" in less than or equal to the ordinal number ω α of steps. This result represents a generalization of the well-known "limit lemma" due to J. R. Shoenfield [Sho-1] and later independently by H. Putnam [Pu] and independently by E. M. Gold [Go]. As an application of this result, we give a recursion theoretic analysis of clopen determinacy: there is a correlation given between the height α of a well-founded tree corresponding to a clopen game $A \subseteq \omega^\omega$ and the Turing degree of a winning strategy f for one of the players--roughly, f can be chosen to be recursive in 0 α and this is the best possible (see § 4 for precise results)
|Keywords||Limit lemma clopen games hyperarithmetic winning strategy trees|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Toshiyasu Arai (1998). Variations on a Theme by Weiermann. Journal of Symbolic Logic 63 (3):897-925.
I. L. Gál, J. B. Rosser & D. Scott (1958). Generalization of a Lemma of G. F. Rose. Journal of Symbolic Logic 23 (2):137-138.
Steffen Lempp & Theodore A. Slaman (1989). A Limit on Relative Genericity in the Recursively Enumerable Sets. Journal of Symbolic Logic 54 (2):376-395.
Douglas Cenzer & Rick L. Smith (1989). On the Ranked Points of a Π01 Set. Journal of Symbolic Logic 54 (3):975 - 991.
Itay Neeman (2006). Determinacy for Games Ending at the First Admissible Relative to the Play. Journal of Symbolic Logic 71 (2):425 - 459.
Lawrence Diffo Lambo & Joël Moulen (2002). Ordinal Equivalence of Power Notions in Voting Games. Theory and Decision 53 (4):313-325.
Peter Clote (1984). A Recursion Theoretic Analysis of the Clopen Ramsey Theorem. Journal of Symbolic Logic 49 (2):376-400.
Alan Hájek & Harris Nover (2008). Complex Expectations. Mind 117 (467):643 - 664.
Added to index2009-01-28
Total downloads6 ( #454,618 of 1,793,278 )
Recent downloads (6 months)2 ( #344,495 of 1,793,278 )
How can I increase my downloads?