Computable shuffle sums of ordinals

Archive for Mathematical Logic 47 (3):211-219 (2008)
  Copy   BIBTEX

Abstract

The main result is that for sets ${S \subseteq \omega + 1}$ , the following are equivalent: The shuffle sum σ(S) is computable.The set S is a limit infimum set, i.e., there is a total computable function g(x, t) such that ${f(x) = \lim inf_t g(x, t)}$ enumerates S.The set S is a limitwise monotonic set relative to 0′, i.e., there is a total 0′-computable function ${\tilde{g}(x, t)}$ satisfying ${\tilde{g}(x, t) \leq \tilde{g}(x, t+1)}$ such that ${{\tilde{f}(x) = \lim_t \tilde{g}(x, t)}}$ enumerates S.Other results discuss the relationship between these sets and the ${\Sigma^0_3}$ sets

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,389

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

Order-Computable Sets.Denis Hirschfeldt, Russell Miller & Sergei Podzorov - 2007 - Notre Dame Journal of Formal Logic 48 (3):317-347.
Bounding Prime Models.Barbara F. Csima, Denis R. Hirschfeldt, Julia F. Knight & Robert I. Soare - 2004 - Journal of Symbolic Logic 69 (4):1117 - 1142.
Derivatives of Computable Functions.Ning Zhong - 1998 - Mathematical Logic Quarterly 44 (3):304-316.
Computability of Measurable Sets Via Effective Topologies.Yongcheng Wu & Decheng Ding - 2006 - Archive for Mathematical Logic 45 (3):365-379.
Η-Representation of Sets and Degrees.Kenneth Harris - 2008 - Journal of Symbolic Logic 73 (4):1097-1121.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
Uncomputably Noisy Ergodic Limits.Jeremy Avigad - 2012 - Notre Dame Journal of Formal Logic 53 (3):347-350.
Computability & Unsolvability.Martin Davis - 1958 - Dover Publications.
Euclidean Functions of Computable Euclidean Domains.Rodney G. Downey & Asher M. Kach - 2011 - Notre Dame Journal of Formal Logic 52 (2):163-172.

Analytics

Added to PP
2013-11-23

Downloads
50 (#232,384)

6 months
1 (#415,900)

Historical graph of downloads
How can I increase my downloads?