Results for 'Computably enumerable sets'

1000+ found
Order:
  1. Randomness and Recursive Enumerability.Siam J. Comput - unknown
    One recursively enumerable real α dominates another one β if there are nondecreasing recursive sequences of rational numbers (a[n] : n ∈ ω) approximating α and (b[n] : n ∈ ω) approximating β and a positive constant C such that for all n, C(α − a[n]) ≥ (β − b[n]). See [R. M. Solovay, Draft of a Paper (or Series of Papers) on Chaitin’s Work, manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1974, p. 215] and [G. (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  2.  14
    Computably enumerable sets below random sets.André Nies - 2012 - Annals of Pure and Applied Logic 163 (11):1596-1610.
    We use Demuth randomness to study strong lowness properties of computably enumerable sets, and sometimes of Δ20 sets. A set A⊆N is called a base for Demuth randomness if some set Y Turing above A is Demuth random relative to A. We show that there is an incomputable, computably enumerable base for Demuth randomness, and that each base for Demuth randomness is strongly jump-traceable. We obtain new proofs that each computably enumerable set (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  3.  22
    Computably enumerable sets and quasi-reducibility.R. Downey, G. LaForte & A. Nies - 1998 - Annals of Pure and Applied Logic 95 (1-3):1-35.
    We consider the computably enumerable sets under the relation of Q-reducibility. We first give several results comparing the upper semilattice of c.e. Q-degrees, RQ, Q, under this reducibility with the more familiar structure of the c.e. Turing degrees. In our final section, we use coding methods to show that the elementary theory of RQ, Q is undecidable.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  4.  15
    The ibT degrees of computably enumerable sets are not dense.George Barmpalias & Andrew E. M. Lewis - 2006 - Annals of Pure and Applied Logic 141 (1-2):51-60.
    We show that the identity bounded Turing degrees of computably enumerable sets are not dense.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  5.  72
    Dynamic properties of computably enumerable sets.Robert I. Soare - 1996 - In S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.), Computability, enumerability, unsolvability: directions in recursion theory. New York: Cambridge University Press. pp. 224--105.
    Direct download  
     
    Export citation  
     
    Bookmark   4 citations  
  6.  39
    Asymptotic density and computably enumerable sets.Rodney G. Downey, Carl G. Jockusch & Paul E. Schupp - 2013 - Journal of Mathematical Logic 13 (2):1350005.
    We study connections between classical asymptotic density, computability and computable enumerability. In an earlier paper, the second two authors proved that there is a computably enumerable set A of density 1 with no computable subset of density 1. In the current paper, we extend this result in three different ways: The degrees of such sets A are precisely the nonlow c.e. degrees. There is a c.e. set A of density 1 with no computable subset of nonzero density. (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  7.  51
    Definable properties of the computably enumerable sets.Leo Harrington & Robert I. Soare - 1998 - Annals of Pure and Applied Logic 94 (1-3):97-125.
    Post in 1944 began studying properties of a computably enumerable set A such as simple, h-simple, and hh-simple, with the intent of finding a property guaranteeing incompleteness of A . From the observations of Post and Myhill , attention focused by the 1950s on properties definable in the inclusion ordering of c.e. subsets of ω, namely E = . In the 1950s and 1960s Tennenbaum, Martin, Yates, Sacks, Lachlan, Shoenfield and others produced a number of elegant results relating (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  8.  64
    Definable encodings in the computably enumerable sets.Peter A. Cholak & Leo A. Harrington - 2000 - Bulletin of Symbolic Logic 6 (2):185-196.
    The purpose of this communication is to announce some recent results on the computably enumerable sets. There are two disjoint sets of results; the first involves invariant classes and the second involves automorphisms of the computably enumerable sets. What these results have in common is that the guts of the proofs of these theorems uses a new form of definable coding for the computably enumerable sets.We will work in the structure (...)
    Direct download (11 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  9.  17
    Differences of Computably Enumerable Sets.A. Nies & S. Lempp - 2000 - Mathematical Logic Quarterly 46 (4):555-562.
    We consider the ower semilattice [MATHEMATICAL SCRIPT CAPITAL D] of differences of c.e. sets under inclusion. It is shown that [MATHEMATICAL SCRIPT CAPITAL D] is not distributive as a semilattice, and that the c.e. sets form a definable subclass.
    Direct download  
     
    Export citation  
     
    Bookmark  
  10.  29
    Orbits of computably enumerable sets: low sets can avoid an upper cone.Russell Miller - 2002 - Annals of Pure and Applied Logic 118 (1-2):61-85.
    We investigate the orbit of a low computably enumerable set under automorphisms of the partial order of c.e. sets under inclusion. Given an arbitrary low c.e. set A and an arbitrary noncomputable c.e. set C, we use the New Extension Theorem of Soare to construct an automorphism of mapping A to a set B such that CTB. Thus, the orbit in of the low set A cannot be contained in the upper cone above C. This complements a (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  11.  39
    The computable Lipschitz degrees of computably enumerable sets are not dense.Adam R. Day - 2010 - Annals of Pure and Applied Logic 161 (12):1588-1602.
    The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  12.  27
    Kolmogorov complexity and computably enumerable sets.George Barmpalias & Angsheng Li - 2013 - Annals of Pure and Applied Logic 164 (12):1187-1200.
  13.  12
    Addendum to “computably enumerable sets and quasi-reducibility”.R. Downey, G. LaForte & A. Nies - 1999 - Annals of Pure and Applied Logic 98 (1-3):295.
  14.  6
    $$sQ_1$$ -degrees of computably enumerable sets.Roland Sh Omanadze - 2023 - Archive for Mathematical Logic 62 (3):401-417.
    We show that the _sQ_-degree of a hypersimple set includes an infinite collection of \(sQ_1\) -degrees linearly ordered under \(\le _{sQ_1}\) with order type of the integers and each c.e. set in these _sQ_-degrees is a hypersimple set. Also, we prove that there exist two c.e. sets having no least upper bound on the \(sQ_1\) -reducibility ordering. We show that the c.e. \(sQ_1\) -degrees are not dense and if _a_ is a c.e. \(sQ_1\) -degree such that \(o_{sQ_1}, then there (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  15.  46
    Isomorphisms of splits of computably enumerable sets.Peter A. Cholak & Leo A. Harrington - 2003 - Journal of Symbolic Logic 68 (3):1044-1064.
    We show that if A and $\widehat{A}$ are automorphic via Φ then the structures $S_{R}(A)$ and $S_{R}(\widehat{A})$ are $\Delta_{3}^{0}-isomorphic$ via an isomorphism Ψ induced by Φ. Then we use this result to classify completely the orbits of hhsimple sets.
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  16.  55
    On the definability of the double jump in the computably enumerable sets.Peter A. Cholak & Leo A. Harrington - 2002 - Journal of Mathematical Logic 2 (02):261-296.
    We show that the double jump is definable in the computably enumerable sets. Our main result is as follows: let [Formula: see text] is the Turing degree of a [Formula: see text] set J ≥T0″}. Let [Formula: see text] such that [Formula: see text] is upward closed in [Formula: see text]. Then there is an ℒ property [Formula: see text] such that [Formula: see text] if and only if there is an A where A ≡T F and (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  17. On the filter of computably enumerable supersets of an r-maximal set.Steffen Lempp, André Nies & D. Reed Solomon - 2001 - Archive for Mathematical Logic 40 (6):415-423.
    We study the filter ℒ*(A) of computably enumerable supersets (modulo finite sets) of an r-maximal set A and show that, for some such set A, the property of being cofinite in ℒ*(A) is still Σ0 3-complete. This implies that for this A, there is no uniformly computably enumerable “tower” of sets exhausting exactly the coinfinite sets in ℒ*(A).
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  18.  27
    Codable sets and orbits of computably enumerable sets.Leo Harrington & Robert I. Soare - 1998 - Journal of Symbolic Logic 63 (1):1-28.
    A set X of nonnegative integers is computably enumerable (c.e.), also called recursively enumerable (r.e.), if there is a computable method to list its elements. Let ε denote the structure of the computably enumerable sets under inclusion, $\varepsilon = (\{W_e\}_{e\in \omega}, \subseteq)$ . We previously exhibited a first order ε-definable property Q(X) such that Q(X) guarantees that X is not Turing complete (i.e., does not code complete information about c.e. sets). Here we show (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  19. Definability, automorphisms, and dynamic properties of computably enumerable sets.Leo Harrington & Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (2):199-213.
    We announce and explain recent results on the computably enumerable (c.e.) sets, especially their definability properties (as sets in the spirit of Cantor), their automorphisms (in the spirit of Felix Klein's Erlanger Programm), their dynamic properties, expressed in terms of how quickly elements enter them relative to elements entering other sets, and the Martin Invariance Conjecture on their Turing degrees, i.e., their information content with respect to relative computability (Turing reducibility).
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  20.  41
    On orbits, of prompt and low computably enumerable sets.Kevin Wald - 2002 - Journal of Symbolic Logic 67 (2):649-678.
    This paper concerns automorphisms of the computably enumerable sets. We prove two results relating semilow sets and prompt degrees via automorphisms, one of which is complementary to a recent result of Downey and Harrington. We also show that the property of effective simplicity is not invariant under automorphism, and that in fact every promptly simple set is automorphic to an effectively simple set. A major technique used in these proofs is a modification of the Harrington-Soare version (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  21.  72
    The complexity of orbits of computably enumerable sets.Peter A. Cholak, Rodney Downey & Leo A. Harrington - 2008 - Bulletin of Symbolic Logic 14 (1):69 - 87.
    The goal of this paper is to announce there is a single orbit of the c.e. sets with inclusion, ε, such that the question of membership in this orbit is ${\Sigma _1^1 }$ -complete. This result and proof have a number of nice corollaries: the Scott rank of ε is $\omega _1^{{\rm{CK}}}$ + 1; not all orbits are elementarily definable; there is no arithmetic description of all orbits of ε; for all finite α ≥ 9, there is a properly (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  22. The http://ars. els-cdn. com/content/image/http://origin-ars. els-cdn. com/content/image/1-s2. 0-S0168007205001429-si1. gif"/> degrees of computably enumerable sets are not dense. [REVIEW]George Barmpalias & Andrew Em Lewis - 2006 - Annals of Pure and Applied Logic 141 (1):51-60.
  23.  34
    Computability, enumerability, unsolvability: directions in recursion theory.S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.) - 1996 - New York: Cambridge University Press.
    The fundamental ideas concerning computation and recursion naturally find their place at the interface between logic and theoretical computer science. The contributions in this book, by leaders in the field, provide a picture of current ideas and methods in the ongoing investigations into the pure mathematical foundations of computability theory. The topics range over computable functions, enumerable sets, degree structures, complexity, subrecursiveness, domains and inductive inference. A number of the articles contain introductory and background material which it is (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  24.  58
    Computability, enumerability, unsolvability, Directions in recursion theory, edited by S. B. Cooper, T. A. Slaman, and S. S. Wainer, London Mathematical Society lecture note series, no. 224, Cambridge University Press, Cambridge, New York, and Oakleigh, Victoria, 1996, vii + 347 pp. - Leo Harrington and Robert I. Soare, Dynamic properties of computably enumerable sets, Pp. 105–121. - Eberhard Herrmann, On the ∀∃-theory of the factor lattice by the major subset relation, Pp. 139–166. - Manuel Lerman, Embeddings into the recursively enumerable degrees, Pp. 185–204. - Xiaoding Yi, Extension of embeddings on the recursively enumerable degrees modulo the cappable degrees, Pp. 313–331. - André Nies, Relativization of structures arising from computability theory. Pp. 219–232. - Klaus Ambos-Spies, Resource-bounded genericity. Pp. 1–59. - Rod Downey, Carl G. Jockusch, and Michael Stob. Array nonrecursive degrees and genericity, Pp. 93–104. - Masahiro Kumabe, Degrees of generic sets, Pp. 167–183. [REVIEW]C. T. Chong - 1999 - Journal of Symbolic Logic 64 (3):1362-1365.
  25.  8
    Definability of recursively enumerable sets in abstract computational complexity theory.Robert E. Byerly - 1984 - Mathematical Logic Quarterly 30 (32‐34):499-503.
  26.  23
    Definability of Recursively Enumerable Sets in Abstract Computational Complexity Theory.Robert E. Byerly - 1984 - Mathematical Logic Quarterly 30 (32-34):499-503.
  27.  7
    The complexity of index sets of classes of computably enumerable equivalence relations.Uri Andrews & Andrea Sorbi - 2016 - Journal of Symbolic Logic 81 (4):1375-1395.
    Let$ \le _c $be computable the reducibility on computably enumerable equivalence relations. We show that for every ceerRwith infinitely many equivalence classes, the index sets$\left\{ {i:R_i \le _c R} \right\}$,$\left\{ {i:R_i \ge _c R} \right\}$, and$\left\{ {i:R_i \equiv _c R} \right\}$are${\rm{\Sigma }}_3^0$complete, whereas in caseRhas only finitely many equivalence classes, we have that$\left\{ {i:R_i \le _c R} \right\}$is${\rm{\Pi }}_2^0$complete, and$\left\{ {i:R \ge _c R} \right\}$ is${\rm{\Sigma }}_2^0$complete. Next, solving an open problem from [1], we prove that the (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  28.  32
    Computably Enumerable Reals and Uniformly Presentable Ideals.S. A. Terwijn & R. Downey - 2002 - Mathematical Logic Quarterly 48 (S1):29-40.
    We study the relationship between a computably enumerable real and its presentations. A set A presents a computably enumerable real α if A is a computably enumerable prefix-free set of strings such that equation image. Note that equation image is precisely the measure of the set of reals that have a string in A as an initial segment. So we will simply abbreviate equation image by μ. It is known that whenever A so presents (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  29.  23
    On isomorphism classes of computably enumerable equivalence relations.Uri Andrews & Serikzhan A. Badaev - 2020 - Journal of Symbolic Logic 85 (1):61-86.
    We examine how degrees of computably enumerable equivalence relations under computable reduction break down into isomorphism classes. Two ceers are isomorphic if there is a computable permutation of ω which reduces one to the other. As a method of focusing on nontrivial differences in isomorphism classes, we give special attention to weakly precomplete ceers. For any degree, we consider the number of isomorphism types contained in the degree and the number of isomorphism types of weakly precomplete ceers contained (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  30.  14
    Weakly precomplete computably enumerable equivalence relations.Serikzhan Badaev & Andrea Sorbi - 2016 - Mathematical Logic Quarterly 62 (1-2):111-127.
    Using computable reducibility ⩽ on equivalence relations, we investigate weakly precomplete ceers (a “ceer” is a computably enumerable equivalence relation on the natural numbers), and we compare their class with the more restricted class of precomplete ceers. We show that there are infinitely many isomorphism types of universal (in fact uniformly finitely precomplete) weakly precomplete ceers, that are not precomplete; and there are infinitely many isomorphism types of non‐universal weakly precomplete ceers. Whereas the Visser space of a precomplete (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  31.  20
    An Interval of Computably Enumerable Isolating Degrees.Matthew C. Salts - 1999 - Mathematical Logic Quarterly 45 (1):59-72.
    We construct computably enumerable degrees a < b such that all computably enumerable degrees c with a < c < b isolate some d. c. e. degree d.
    Direct download  
     
    Export citation  
     
    Bookmark  
  32.  17
    A computably enumerable vector space with the strong antibasis property.L. R. Galminas - 2000 - Archive for Mathematical Logic 39 (8):605-629.
    Downey and Remmel have completely characterized the degrees of c.e. bases for c.e. vector spaces (and c.e. fields) in terms of weak truth table degrees. In this paper we obtain a structural result concerning the interaction between the c.e. Turing degrees and the c.e. weak truth table degrees, which by Downey and Remmel's classification, establishes the existence of c.e. vector spaces (and fields) with the strong antibasis property (a question which they raised). Namely, we construct c.e. sets $B<_{\rm T}A$ (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  33.  17
    Soare Robert I.. Recursively enumerable sets and degrees. A study of computable functions and computably generated sets. Perspectives in mathematical logic. Springer-Verlag, Berlin, Heidelberg, New York, etc., 1987, xviii + 437 pp. [REVIEW]Eberhard Herrmann & Rodney Downey - 1990 - Journal of Symbolic Logic 55 (1):356-357.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  34.  13
    Computable limits and colimits in categories of partial enumerated sets.Andrzej Orlicki - 1993 - Mathematical Logic Quarterly 39 (1):181-196.
    Computable limits and colimits are “recursive counterparts” of the suitable classical concepts from category theory. We present mainly some interesting problems related to computable products. Moreover, some “computable counterparts” of well-known classical facts from category theory are given. MSC: 03D45, 18A30.
    Direct download  
     
    Export citation  
     
    Bookmark  
  35.  28
    Every incomplete computably enumerable truth-table degree is branching.Peter A. Fejer & Richard A. Shore - 2001 - Archive for Mathematical Logic 40 (2):113-123.
    If r is a reducibility between sets of numbers, a natural question to ask about the structure ? r of the r-degrees containing computably enumerable sets is whether every element not equal to the greatest one is branching (i.e., the meet of two elements strictly above it). For the commonly studied reducibilities, the answer to this question is known except for the case of truth-table (tt) reducibility. In this paper, we answer the question in the tt (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  36.  34
    Ramsey's theorem for computably enumerable colorings.Tamara J. Hummel & Carl G. Jockusch - 2001 - Journal of Symbolic Logic 66 (2):873-880.
    It is shown that for each computably enumerable set P of n-element subsets of ω there is an infinite Π 0 n set $A \subseteq \omega$ such that either all n-element subsets of A are in P or no n-element subsets of A are in P. An analogous result is obtained with the requirement that A be Π 0 n replaced by the requirement that the jump of A be computable from 0 (n) . These results are best (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  37.  12
    1-Generic splittings of computably enumerable degrees.Guohua Wu - 2006 - Annals of Pure and Applied Logic 138 (1):211-219.
    Say a set Gω is 1-generic if for any eω, there is a string σG such that {e}σ↓ or τσ↑). It is known that can be split into two 1-generic degrees. In this paper, we generalize this and prove that any nonzero computably enumerable degree can be split into two 1-generic degrees. As a corollary, no two computably enumerable degrees bound the same class of 1-generic degrees.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  38. Review: Robert I. Soare, Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets[REVIEW]Eberhard Herrmann & Rodney Downey - 1990 - Journal of Symbolic Logic 55 (1):356-357.
  39. called degrees. Post was particularly interested in computability from sets which are par-tially generated by a computer, namely, those for which the elements of the set can be enumerated by a computer. These sets are called (recursively) enu-merable, as are their degrees. He showed [20] that the enumerable degrees. [REVIEW]J. Knight, A. Kucera & R. Shore - 1995 - Bulletin of Symbolic Logic 1 (2).
  40.  7
    Minimal weak truth table degrees and computably enumerable Turing degrees.R. G. Downey - 2020 - Providence, RI: American Mathematical Society. Edited by Keng Meng Ng & Reed Solomon.
    Informal construction -- Formal construction -- Limiting results.
    Direct download  
     
    Export citation  
     
    Bookmark  
  41.  5
    A hierarchy of Turing degrees: a transfinite hierarchy of lowness notions in the computably enumerable degrees, unifying classes, and natural definability.R. G. Downey - 2020 - Princeton: Princeton University Press. Edited by Noam Greenberg.
    This book presents new results in computability theory, a branch of mathematical logic and computer science that has become increasingly relevant in recent years. The field's connections with disparate areas of mathematical logic and mathematics more generally have grown deeper, and now have a variety of applications in topology, group theory, and other subfields. This monograph establishes new directions in the field, blending classic results with modern research areas such as algorithmic randomness. The significance of the book lies not only (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  42.  58
    A limit on relative genericity in the recursively enumerable sets.Steffen Lempp & Theodore A. Slaman - 1989 - Journal of Symbolic Logic 54 (2):376-395.
    Work in the setting of the recursively enumerable sets and their Turing degrees. A set X is low if X', its Turning jump, is recursive in $\varnothing'$ and high if X' computes $\varnothing''$ . Attempting to find a property between being low and being recursive, Bickford and Mills produced the following definition. W is deep, if for each recursively enumerable set A, the jump of $A \bigoplus W$ is recursive in the jump of A. We prove that (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  43.  5
    Non-empty open intervals of computably enumerable sQ 1-degrees.Roland Omanadze & Irakli Chitaia - forthcoming - Logic Journal of the IGPL.
    We prove that if $A$, $B$ are noncomputable c.e. sets, $A<_{sQ_{1}}B$ and [($B$ is not simple and $A\oplus B\leq _{sQ_{1}}B$) or $B\equiv _{sQ_{1}}B\times \omega $], then there exist infinitely many pairwise $sQ_{1}$-incomparable c.e. sets $\{C_{i}\}_{i\in \omega }$ such that $A<_{sQ_{1}}C_{i}<_{sQ_{1}}B$, for all $i\in \omega $. We also show that there exist infinite collections of $sQ_{1}$-degrees $\{\boldsymbol {a_{i}}\}_{i\in \omega }$ and $\{\boldsymbol {b_{i}}\}_{i\in \omega }$ such that for every $i, j,$ (1) $\boldsymbol {a_{i}}<_{sQ_{1}}\boldsymbol {a_{i+1}}$, $\boldsymbol {b_{j+1}}<_{sQ_{1}}\boldsymbol {b_{j}}$ and $\boldsymbol (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  44.  68
    Enumerations in computable structure theory.Sergey Goncharov, Valentina Harizanov, Julia Knight, Charles McCoy, Russell Miller & Reed Solomon - 2005 - Annals of Pure and Applied Logic 136 (3):219-246.
    We exploit properties of certain directed graphs, obtained from the families of sets with special effective enumeration properties, to generalize several results in computable model theory to higher levels of the hyperarithmetical hierarchy. Families of sets with such enumeration features were previously built by Selivanov, Goncharov, and Wehner. For a computable successor ordinal α, we transform a countable directed graph into a structure such that has a isomorphic copy if and only if has a computable isomorphic copy.A computable (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   18 citations  
  45.  12
    Difference sets and computability theory.Rod Downey, Zoltán Füredi, Carl G. Jockusch & Lee A. Rubel - 1998 - Annals of Pure and Applied Logic 93 (1-3):63-72.
    For a set A of non-negative integers, let D be the set of non-negative differences of elements of A. Clearly, if A is computable, then D is computably enumerable. We show that every simple set which contains 0 is the difference set of some computable set and that every computably enumerable set is computably isomorphic to the difference set of some computable set. Also, we prove that there is a computable set which is the difference (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  46.  42
    Effectively closed sets and enumerations.Paul Brodhead & Douglas Cenzer - 2008 - Archive for Mathematical Logic 46 (7-8):565-582.
    An effectively closed set, or ${\Pi^{0}_{1}}$ class, may viewed as the set of infinite paths through a computable tree. A numbering, or enumeration, is a map from ω onto a countable collection of objects. One numbering is reducible to another if equality holds after the second is composed with a computable function. Many commonly used numberings of ${\Pi^{0}_{1}}$ classes are shown to be mutually reducible via a computable permutation. Computable injective numberings are given for the family of ${\Pi^{0}_{1}}$ classes and (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  47.  22
    Computability in structures representing a Scott set.Alex M. McAllister - 2001 - Archive for Mathematical Logic 40 (3):147-165.
    Continuing work begun in [10], we utilize a notion of forcing for which the generic objects are structures and which allows us to determine whether these “generic” structures compute certain sets and enumerations. The forcing conditions are bounded complexity types which are consistent with a given theory and are elements of a given Scott set. These generic structures will “represent” this given Scott set, in the sense that the structure has a certain weak saturation property with respect to bounded (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  48.  58
    A random set which only computes strongly jump-traceable C.e. Sets.Noam Greenberg - 2011 - Journal of Symbolic Logic 76 (2):700 - 718.
    We prove that there is a ${\mathrm{\Delta }}_{2}^{0}$ , 1-random set Y such that every computably enumerable set which is computable from Y is strongly jump-traceable. We also show that for every order function h there is an ω-c.e. random set Y such that every computably enumerable set which is computable from Y is h-jump-traceable. This establishes a correspondence between rates of jump-traceability and computability from ω-c.e. random sets.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  49.  23
    Traces, traceability, and lattices of traces under the set theoretic inclusion.Gunther Mainhardt - 2013 - Archive for Mathematical Logic 52 (7-8):847-869.
    Let a trace be a computably enumerable set of natural numbers such that V[m]={n:〈n,m〉∈V}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${V^{[m]} = \{n : \langle n, m\rangle \in V \}}$$\end{document} is finite for all m, where 〈.,.〉\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\langle^{.},^{.}\rangle}$$\end{document} denotes an appropriate pairing function. After looking at some basic properties of traces like that there is no uniform enumeration of all traces, we prove varied results on traceability and variants (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  50.  94
    Computability, an introduction to recursive function theory.Nigel Cutland - 1980 - New York: Cambridge University Press.
    What can computers do in principle? What are their inherent theoretical limitations? These are questions to which computer scientists must address themselves. The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function: intuitively a function whose values can be calculated in an effective or automatic way. This book is an introduction to computability theory (or recursion theory as it is traditionally known to mathematicians). Dr Cutland (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   27 citations  
1 — 50 / 1000