24 found
Order:
Disambiguations
Russell Miller [24]Russell G. Miller [1]Russell J. Miller [1]
  1.  7
    A Computable Functor From Graphs to Fields.Russell Miller, Bjorn Poonen, Hans Schoutens & Alexandra Shlapentokh - 2018 - Journal of Symbolic Logic 83 (1):326-348.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  2.  5
    Computable Functors and Effective Interpretability.Matthew Harrison-Trainor, Alexander Melnikov, Russell Miller & Antonio Montalbán - 2017 - Journal of Symbolic Logic 82 (1):77-97.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  3.  3
    Turing Degree Spectra of Differentially Closed Fields.David Marker & Russell Miller - 2017 - Journal of Symbolic Logic 82 (1):1-25.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  4.  13
    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 structure is (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  5.  32
    Degrees of Categoricity of Computable Structures.Ekaterina B. Fokina, Iskander Kalimullin & Russell Miller - 2010 - Archive for Mathematical Logic 49 (1):51-67.
    Defining the degree of categoricity of a computable structure ${\mathcal{M}}$ to be the least degree d for which ${\mathcal{M}}$ is d-computably categorical, we investigate which Turing degrees can be realized as degrees of categoricity. We show that for all n, degrees d.c.e. in and above 0 (n) can be so realized, as can the degree 0 (ω).
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  6.  20
    The Basic Theory of Infinite Time Register Machines.Merlin Carl, Tim Fischbach, Peter Koepke, Russell Miller, Miriam Nasfi & Gregor Weckbecker - 2010 - Archive for Mathematical Logic 49 (2):249-273.
    Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is set (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  7.  16
    D-Computable Categoricity for Algebraic Fields.Russell Miller - 2009 - Journal of Symbolic Logic 74 (4):1325 - 1351.
    We use the Low Basis Theorem of Jockusch and Soare to show that all computable algebraic fields are d-computably categorical for a particular Turing degree d with d' = θ", but that not all such fields are 0'-computably categorical. We also prove related results about algebraic fields with splitting algorithms, and fields of finite transcendence degree over ℚ.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  8.  15
    The Δ02-Spectrum of a Linear Order.Russell Miller - 2001 - Journal of Symbolic Logic 66 (2):470 - 486.
    Slaman and Wehner have constructed structures which distinguish the computable Turing degree 0 from the noncomputable degrees, in the sense that the spectrum of each structure consists precisely of the noncomputable degrees. Downey has asked if this can be done for an ordinary type of structure such as a linear order. We show that there exists a linear order whose spectrum includes every noncomputable Δ 0 2 degree, but not 0. Since our argument requires the technique of permitting below a (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  9.  20
    Computable Categoricity of Trees of Finite Height.Steffen Lempp, Charles McCoy, Russell Miller & Reed Solomon - 2005 - Journal of Symbolic Logic 70 (1):151-215.
    We characterize the structure of computably categorical trees of finite height, and prove that our criterion is both necessary and sufficient. Intuitively, the characterization is easiest to express in terms of isomorphisms of (possibly infinite) trees, but in fact it is equivalent to a Σ03-condition. We show that all trees which are not computably categorical have computable dimension ω. Finally, we prove that for every n≥ 1 in ω, there exists a computable tree of finite height which is δ0n+1-categorical but (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  10.  1
    The -Spectrum of a Linear Order.Russell Miller - 2001 - Journal of Symbolic Logic 66 (2):470-486.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  11.  13
    Order-Computable Sets.Denis Hirschfeldt, Russell Miller & Sergei Podzorov - 2007 - Notre Dame Journal of Formal Logic 48 (3):317-347.
    We give a straightforward computable-model-theoretic definition of a property of \Delta^0_2 sets called order-computability. We then prove various results about these sets which suggest that, simple though the definition is, the property defies any easy characterization in pure computability theory. The most striking example is the construction of two computably isomorphic c.e. sets, one of which is order-computable and the other not.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  12.  13
    Computability of Fraïssé Limits.Barbara F. Csima, Valentina S. Harizanov, Russell Miller & Antonio Montalbán - 2011 - Journal of Symbolic Logic 76 (1):66 - 93.
    Fraïssé studied countable structures S through analysis of the age of S i.e., the set of all finitely generated substructures of S. We investigate the effectiveness of his analysis, considering effectively presented lists of finitely generated structures and asking when such a list is the age of a computable structure. We focus particularly on the Fraïssé limit. We also show that degree spectra of relations on a sufficiently nice Fraïssé limit are always upward closed unless the relation is definable by (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  13.  8
    The Computable Dimension of Trees of Infinite Height.Russell Miller - 2005 - Journal of Symbolic Logic 70 (1):111-141.
    We prove that no computable tree of infinite height is computably categorical, and indeed that all such trees have computable dimension ω. Moreover, this dimension is effectively ω, in the sense that given any effective listing of computable presentations of the same tree, we can effectively find another computable presentation of it which is not computably isomorphic to any of the presentations on the list.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  14.  2
    Borel Functors and Infinitary Interpretations.Matthew Harrison-Trainor, Russell Miller & Antonio Montalbán - 2018 - Journal of Symbolic Logic 83 (4):1434-1456.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  15.  3
    Degree Spectra of Real Closed Fields.Russell Miller & Victor Ocasio González - 2019 - Archive for Mathematical Logic 58 (3-4):387-411.
    Several researchers have recently established that for every Turing degree \, the real closed field of all \-computable real numbers has spectrum \. We investigate the spectra of real closed fields further, focusing first on subfields of the field \ of computable real numbers, then on archimedean real closed fields more generally, and finally on non-archimedean real closed fields. For each noncomputable, computably enumerable set C, we produce a real closed C-computable subfield of \ with no computable copy. Then we (...)
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  16.  22
    Post’s Problem for Ordinal Register Machines: An Explicit Approach.Joel David Hamkins & Russell G. Miller - 2009 - Annals of Pure and Applied Logic 160 (3):302-309.
    We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  17.  13
    Low₅ Boolean Subalgebras and Computable Copies.Russell Miller - 2011 - Journal of Symbolic Logic 76 (3):1061 - 1074.
    It is known that the spectrum of a Boolean algebra cannot contain a low₄ degree unless it also contains the degree 0; it remains open whether the same holds for low₅ degrees. We address the question differently, by considering Boolean subalgebras of the computable atomless Boolean algebra B. For such subalgebras A, we show that it is possible for the spectrum of the unary relation A on B to contain a low₅ degree without containing 0.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  18.  8
    Complexity of Equivalence Relations and Preorders From Computability Theory.Egor Ianovski, Russell Miller, Keng Meng Ng & André Nies - 2014 - Journal of Symbolic Logic 79 (3):859-881.
  19.  13
    San Antonio Convention Center San Antonio, Texas January 14–15, 2006.Douglas Cenzer, C. Ward Henson, Michael C. Laskowski, Alain Louveau, Russell Miller, Itay Neeman, Sergei Starchenko & Valentina Harizanov - 2006 - Bulletin of Symbolic Logic 12 (4).
    Direct download  
     
    Export citation  
     
    Bookmark  
  20.  4
    Classifications of Computable Structures.Karen Lange, Russell Miller & Rebecca M. Steiner - 2018 - Notre Dame Journal of Formal Logic 59 (1):35-59.
    Let K be a family of structures, closed under isomorphism, in a fixed computable language. We consider effective lists of structures from K such that every structure in K is isomorphic to exactly one structure on the list. Such a list is called a computable classification of K, up to isomorphism. Using the technique of Friedberg enumeration, we show that there is a computable classification of the family of computable algebraic fields and that with a 0'-oracle, we can obtain similar (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  21.  10
    Definable Incompleteness and Friedberg Splittings.Russell Miller - 2002 - Journal of Symbolic Logic 67 (2):679-696.
    We define a property R(A 0 , A 1 ) in the partial order E of computably enumerable sets under inclusion, and prove that R implies that A 0 is noncomputable and incomplete. Moreover, the property is nonvacuous, and the A 0 and A 1 which we build satisfying R form a Friedberg splitting of their union A, with A 1 prompt and A promptly simple. We conclude that A 0 and A 1 lie in distinct orbits under automorphisms of (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  22.  10
    Flashing Out or Fleshing Out? A Developmental Perspective on a Universal Model of Reading.Bruce D. Homer, Russell Miller & Seamus Donnelly - 2012 - Behavioral and Brain Sciences 35 (5):289-290.
    The principles for universal reading models proposed by Frost correspond to developmental theories, in which neurocognitive constraints and cultural experiences shape development. We question his contention that Hebrew word identification is fundamentally about roots, excluding verbal and nominal word-pattern morphemes; and we propose that readers use all information available in stimuli, adjusting for volume and usefulness.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  23.  7
    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 result of Harrington, (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  24.  4
    The $Delta^0_2$-Spectrum of a Linear Order.Russell Miller - 2001 - Journal of Symbolic Logic 66 (2):470-486.
    Slaman and Wehner have constructed structures which distinguish the computable Turing degree 0 from the noncomputable degrees, in the sense that the spectrum of each structure consists precisely of the noncomputable degrees. Downey has asked if this can be done for an ordinary type of structure such as a linear order. We show that there exists a linear order whose spectrum includes every noncomputable $\Delta^0_2$ degree, but not 0. Since our argument requires the technique of permitting below a $\Delta^0_2$ set, (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark