A generalization of the limit lemma and clopen games

Journal of Symbolic Logic 51 (2):273-291 (1986)
  Copy   BIBTEX


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)



    Upload a copy of this work     Papers currently archived: 77,985

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles


Added to PP

30 (#397,267)

6 months
1 (#485,425)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Thinking may be more than computing.Peter Kugel - 1986 - Cognition 22 (2):137-198.

Add more citations

References found in this work

Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
Recursive well-founded orderings.Keh-Hsun Chen - 1978 - Annals of Mathematical Logic 13 (2):117-147.
Degrees of Unsolvability.Joseph R. Shoenfield - 1975 - Studia Logica 34 (3):284-288.
Recursice well-founded orderings.D. -H. Chen - 1978 - Annals of Mathematical Logic 13 (2):117.

Add more references