21 found
Order:
Disambiguations
Daniel Turetsky [10]Dan Turetsky [8]Daniel D. Turetsky [3]
See also
  1.  4
    Punctual Categoricity and Universality.Rod Downey, Noam Greenberg, Alexander Melnikov, Keng Meng Ng & Daniel Turetsky - 2020 - Journal of Symbolic Logic 85 (4):1427-1466.
    We describe punctual categoricity in several natural classes, including binary relational structures and mono-unary functional structures. We prove that every punctually categorical structure in a finite unary language is ${\text {PA}}$-categorical, and we show that this upper bound is tight. We also construct an example of a punctually categorical structure whose degree of categoricity is $0''$. We also prove that, with a bit of work, the latter result can be pushed beyond $\Delta ^1_1$, thus showing that punctually categorical structures can (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  2.  20
    Computing K-Trivial Sets by Incomplete Random Sets.Laurent Bienvenu, Adam R. Day, Noam Greenberg, Antonín Kučera, Joseph S. Miller, André Nies & Dan Turetsky - 2014 - Bulletin of Symbolic Logic 20 (1):80-90.
    EveryK-trivial set is computable from an incomplete Martin-Löf random set, i.e., a Martin-Löf random set that does not compute the halting problem.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  3.  13
    Linear Orders Realized by C.E. Equivalence Relations.Ekaterina Fokina, Bakhadyr Khoussainov, Pavel Semukhin & Daniel Turetsky - 2016 - Journal of Symbolic Logic 81 (2):463-482.
    LetEbe a computably enumerable equivalence relation on the setωof natural numbers. We say that the quotient set$\omega /E$realizesa linearly ordered set${\cal L}$if there exists a c.e. relation ⊴ respectingEsuch that the induced structure is isomorphic to${\cal L}$. Thus, one can consider the class of all linearly ordered sets that are realized by$\omega /E$; formally,${\cal K}\left = \left\{ {{\cal L}\,|\,{\rm{the}}\,{\rm{order}}\, - \,{\rm{type}}\,{\cal L}\,{\rm{is}}\,{\rm{realized}}\,{\rm{by}}\,E} \right\}$. In this paper we study the relationship between computability-theoretic properties ofEand algebraic properties of linearly ordered sets realized (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  4.  4
    Relationships Between Computability-Theoretic Properties of Problems.Rod Downey, Noam Greenberg, Matthew Harrison-Trainor, Ludovic Patey & Dan Turetsky - 2022 - Journal of Symbolic Logic 87 (1):47-71.
    A problem is a multivalued function from a set of instances to a set of solutions. We consider only instances and solutions coded by sets of integers. A problem admits preservation of some computability-theoretic weakness property if every computable instance of the problem admits a solution relative to which the property holds. For example, cone avoidance is the ability, given a noncomputable set A and a computable instance of a problem ${\mathsf {P}}$, to find a solution relative to which A (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  5
    Scott Complexity of Countable Structures.Rachael Alvir, Noam Greenberg, Matthew Harrison-Trainor & Dan Turetsky - 2021 - Journal of Symbolic Logic 86 (4):1706-1720.
    We define the Scott complexity of a countable structure to be the least complexity of a Scott sentence for that structure. This is a finer notion of complexity than Scott rank: it distinguishes between whether the simplest Scott sentence is $\Sigma _{\alpha }$, $\Pi _{\alpha }$, or $\mathrm {d-}\Sigma _{\alpha }$. We give a complete classification of the possible Scott complexities, including an example of a structure whose simplest Scott sentence is $\Sigma _{\lambda + 1}$ for $\lambda $ a limit (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  6.  3
    Coding in the Automorphism Group of a Computably Categorical Structure.Dan Turetsky - 2020 - Journal of Mathematical Logic 20 (3):2050016.
    Using new techniques for controlling the categoricity spectrum of a structure, we construct a structure with degree of categoricity but infinite spectral dimension, answering a question of Bazhenov, Kalimullin and Yamaleev. Using the same techniques, we construct a computably categorical structure of non-computable Scott rank.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  7.  8
    Strong Jump-Traceability.Noam Greenberg & Dan Turetsky - 2018 - Bulletin of Symbolic Logic 24 (2):147-164.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  8.  11
    Characterizing Lowness for Demuth Randomness.Laurent Bienvenu, Rod Downey, Noam Greenberg, André Nies & Dan Turetsky - 2014 - Journal of Symbolic Logic 79 (2):526-560.
    We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15]. We fully characterize lowness for Demuth randomness using an appropriate notion of traceability. Central to this characterization is a partial relativization of Demuth randomness, which may be more natural than the fully relativized version. We also show that an oracle is low for weak Demuth randomness if and only if it is computable.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  9.  43
    Decidability and Computability of Certain Torsion-Free Abelian Groups.Rodney G. Downey, Sergei S. Goncharov, Asher M. Kach, Julia F. Knight, Oleg V. Kudinov, Alexander G. Melnikov & Daniel Turetsky - 2010 - Notre Dame Journal of Formal Logic 51 (1):85-96.
    We study completely decomposable torsion-free abelian groups of the form $\mathcal{G}_S := \oplus_{n \in S} \mathbb{Q}_{p_n}$ for sets $S \subseteq \omega$. We show that $\mathcal{G}_S$has a decidable copy if and only if S is $\Sigma^0_2$and has a computable copy if and only if S is $\Sigma^0_3$.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  10.  32
    Limitwise Monotonic Functions, Sets, and Degrees on Computable Domains.Asher M. Kach & Daniel Turetsky - 2010 - Journal of Symbolic Logic 75 (1):131-154.
    We extend the notion of limitwise monotonic functions to include arbitrary computable domains. We then study which sets and degrees are support increasing limitwise monotonic on various computable domains. As applications, we provide a characterization of the sets S with computable increasing η-representations using support increasing limitwise monotonic sets on ℚ and note relationships between the class of order-computable sets and the class of support increasing limitwise monotonic sets on certain domains.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  11.  18
    Lowness for Effective Hausdorff Dimension.Steffen Lempp, Joseph S. Miller, Keng Meng Ng, Daniel D. Turetsky & Rebecca Weber - 2014 - Journal of Mathematical Logic 14 (2):1450011.
    We examine the sequences A that are low for dimension, i.e. those for which the effective dimension relative to A is the same as the unrelativized effective dimension. Lowness for dimension is a weakening of lowness for randomness, a central notion in effective randomness. By considering analogues of characterizations of lowness for randomness, we show that lowness for dimension can be characterized in several ways. It is equivalent to lowishness for randomness, namely, that every Martin-Löf random sequence has effective dimension (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  12.  91
    S. S. Goncharov. Autostability and Computable Families of Constructivizations. Algebra and Logic, Vol. 14 , No. 6, Pp. 392–409. - S. S. Goncharov. The Quantity of Nonautoequivalent Constructivizations. Algebra and Logic, Vol. 16 , No. 3, Pp. 169–185. - S. S. Goncharov and V. D. Dzgoev. Autostability of Models. Algebra and Logic, Vol. 19 , No. 1, Pp. 28–37. - J. B. Remmel. Recursively Categorical Linear Orderings. Proceedings of the American Mathematical Society, Vol. 83 , No. 2, Pp. 387–391. - Terrence Millar. Recursive Categoricity and Persistence. The Journal of Symbolic Logic, Vol. 51 , No. 2, Pp. 430–434. - Peter Cholak, Segey Goncharov, Bakhadyr Khoussainov and Richard A. Shore. Computably Categorical Structures and Expansions by Constants. The Journal of Symbolic Logic, Vol. 64 , No. 1, Pp. 13–137. - Peter Cholak, Richard A. Shore and Reed Solomon. A Computably Stable Structure with No Scott Family of Finitary Formulas. Archive for Mathematical Logic, Vol. 45 , No. 5, Pp. 519–538. [REVIEW]Daniel Turetsky - 2012 - Bulletin of Symbolic Logic 18 (1):131-134.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  13.  2
    Structural Highness Notions.Wesley Calvert, Johanna N. Y. Franklin & Dan Turetsky - forthcoming - Journal of Symbolic Logic:1-33.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14.  58
    Two More Characterizations of K-Triviality.Noam Greenberg, Joseph S. Miller, Benoit Monin & Daniel Turetsky - 2018 - Notre Dame Journal of Formal Logic 59 (2):189-195.
    We give two new characterizations of K-triviality. We show that if for all Y such that Ω is Y-random, Ω is -random, then A is K-trivial. The other direction was proved by Stephan and Yu, giving us the first titular characterization of K-triviality and answering a question of Yu. We also prove that if A is K-trivial, then for all Y such that Ω is Y-random, ≡LRY. This answers a question of Merkle and Yu. The other direction is immediate, so (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  15.  7
    Non-Density in Punctual Computability.Noam Greenberg, Matthew Harrison-Trainor, Alexander Melnikov & Dan Turetsky - 2021 - Annals of Pure and Applied Logic 172 (9):102985.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  16. Several Papers Concerning Computable Categoricity.Daniel Turetsky - 2012 - Bulletin of Symbolic Logic 18 (1):131.
  17.  31
    Galvin’s “Racing Pawns” Game, Internal Hyperarithmetic Comprehension, and the Law of Excluded Middle.Chris Conidis, Noam Greenberg & Daniel Turetsky - 2013 - Notre Dame Journal of Formal Logic 54 (2):233-252.
    We show that the fact that the first player wins every instance of Galvin’s “racing pawns” game is equivalent to arithmetic transfinite recursion. Along the way we analyze the satisfaction relation for infinitary formulas, of “internal” hyperarithmetic comprehension, and of the law of excluded middle for such formulas.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  18.  12
    Computability-Theoretic Categoricity and Scott Families.Ekaterina Fokina, Valentina Harizanov & Daniel Turetsky - 2019 - Annals of Pure and Applied Logic 170 (6):699-717.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  19.  16
    Computability and Uncountable Linear Orders II: Degree Spectra.Noam Greenberg, Asher M. Kach, Steffen Lempp & Daniel D. Turetsky - 2015 - Journal of Symbolic Logic 80 (1):145-178.
  20.  13
    Computability and Uncountable Linear Orders I: Computable Categoricity.Noam Greenberg, Asher M. Kach, Steffen Lempp & Daniel D. Turetsky - 2015 - Journal of Symbolic Logic 80 (1):116-144.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  21.  5
    Uniform Procedures in Uncountable Structures.Noam Greenberg, Alexander G. Melnikov, Julia F. Knight & Daniel Turetsky - 2018 - Journal of Symbolic Logic 83 (2):529-550.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark