Results for 'Andr�� Nies'

1000+ found
Order:
  1.  12
    André Nies. Lowness Properties and Randomness. Advances in Mathematics, Vol. 197 , No. 1, Pp. 274–305. - Bjørn Kjos-Hanssen, André Nies, and Frank Stephan. Lowness for the Class of Schnorr Random Reals. SIAM Journal on Computing, Vol. 35 , No. 3, Pp. 647–657. - Noam Greenberg and Joseph S. Miller. Lowness for Kurtz Randomness. The Journal of Symbolic Logic, Vol. 74 , No. 2, Pp. 665–678. - Laurent Bienvenu and Joseph S. Miller. Randomness and Lowness Notions Via Open Covers. Annals of Pure and Applied Logic, Vol. 163 , No. 5, Pp. 506–518. - Johanna N. Y. Franklin, Frank Stephan, and Liang. Yu Relativizations of Randomness and Genericity Notions. The Bulletin of the London Mathematical Society, Vol. 43 , No. 4, Pp. 721–733. - George Barmpalias, Joseph S. Miller, and André Nies. Randomness Notions and Partial Relativization. Israel Journal of Mathematics, Vol. 191 , No. 2, Pp. 791–816. [REVIEW]Johanna N. Y. Franklin - 2013 - Bulletin of Symbolic Logic 19 (1):115-118.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  2.  1
    André Nies. Computability and Randomness. Oxford Logic Guides, Vol. 51. Oxford University Press, Oxford, 2009, Xv + 433 Pp. [REVIEW]Anthony Morphett - 2010 - Bulletin of Symbolic Logic 16 (1):85-87.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  3.  2
    Computability and Randomness.André Nies - 2008 - Oxford, England: Oxford University Press UK.
    The interplay between computability and randomness has been an active area of research in recent years, reflected by ample funding in the USA, numerous workshops, and publications on the subject. The complexity and the randomness aspect of a set of natural numbers are closely related. Traditionally, computability theory is concerned with the complexity aspect. However, computability theoretic tools can also be used to introduce mathematical counterparts for the intuitive notion of randomness of a set. Recent research shows that, conversely, concepts (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   21 citations  
  4.  52
    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.
  5.  48
    Reviewed Work(S): Lowness Properties and Randomness. Advances in Mathematics, Vol. 197 by André Nies; Lowness for the Class of Schnorr Random Reals. SIAM Journal on Computing, Vol. 35 by Bjørn Kjos-Hanssen; André Nies; Frank Stephan; Lowness for Kurtz Randomness. The Journal of Symbolic Logic, Vol. 74 by Noam Greenberg; Joseph S. Miller; Randomness and Lowness Notions Via Open Covers. Annals of Pure and Applied Logic, Vol. 163 by Laurent Bienvenu; Joseph S. Miller; Relativizations of Randomness and Genericity Notions. The Bulletin of the London Mathematical Society, Vol. 43 by Johanna N. Y. Franklin; Frank Stephan; Liang Yu; Randomness Notions and Partial Relativization. Israel Journal of Mathematics, Vol. 191 by George Barmpalias; Joseph S. Miller; André Nies[REVIEW]Johanna N. Y. Franklin - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
    Review by: Johanna N. Y. Franklin The Bulletin of Symbolic Logic, Volume 19, Issue 1, Page 115-118, March 2013.
    Direct download  
     
    Export citation  
     
    Bookmark  
  6. The Association for Symbolic Logic Publishes Analytical Reviews of Selected Books and Articles in the Field of Symbolic Logic. The Reviews Were Published in The Journal of Symbolic Logic From the Founding of the Journal in 1936 Until the End of 1999. The Association Moved the Reviews to This Bulletin, Beginning in 2000. The Reviews Section is Edited by Steve Awodey (Managing Editor). John Baldwin, John. [REVIEW]Burgess Mark Colyvan Anuj Dawar Mirna, Marcelo Fiore Dzamonja, Hannes Leitgeb, Roger Maddux, Andre Nies Carsten Schurmann, Kai Wehmeier & Matthias Wille Au - 2009 - Bulletin of Symbolic Logic 15 (2).
  7.  4
    Coarse Groups, and the Isomorphism Problem for Oligomorphic Groups.André Nies, Philipp Schlicht & Katrin Tent - forthcoming - Journal of Mathematical Logic.
    Let S∞ denote the topological group of permutations of the natural numbers. A closed subgroup G of S∞ is called oligomorphic if for each n, its natural action on n-tuples of natural numbers has onl...
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  8.  49
    Describing Groups.André Nies - 2007 - Bulletin of Symbolic Logic 13 (3):305-339.
    Two ways of describing a group are considered. 1. A group is finite-automaton presentable if its elements can be represented by strings over a finite alphabet, in such a way that the set of representing strings and the group operation can be recognized by finite automata. 2. An infinite f.g. group is quasi-finitely axiomatizable if there is a description consisting of a single first-order sentence, together with the information that the group is finitely generated. In the first part of the (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  9.  8
    A New Spectrum of Recursive Models.André Nies - 1999 - Notre Dame Journal of Formal Logic 40 (3):307-314.
    We describe a strongly minimal theory S in an effective language such that, in the chain of countable models of S, only the second model has a computable presentation. Thus there is a spectrum of an -categorical theory which is neither upward nor downward closed. We also give an upper bound on the complexity of spectra.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  10.  27
    Computable Models of Theories with Few Models.Bakhadyr Khoussainov, Andre Nies & Richard A. Shore - 1997 - Notre Dame Journal of Formal Logic 38 (2):165-178.
    In this paper we investigate computable models of -categorical theories and Ehrenfeucht theories. For instance, we give an example of an -categorical but not -categorical theory such that all the countable models of except its prime model have computable presentations. We also show that there exists an -categorical but not -categorical theory such that all the countable models of except the saturated model, have computable presentations.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   24 citations  
  11.  24
    Parameter Definability in the Recursively Enumerable Degrees.André Nies - 2003 - Journal of Mathematical Logic 3 (01):37-65.
    The biinterpretability conjecture for the r.e. degrees asks whether, for each sufficiently large k, the [Formula: see text] relations on the r.e. degrees are uniformly definable from parameters. We solve a weaker version: for each k ≥ 7, the [Formula: see text] relations bounded from below by a nonzero degree are uniformly definable. As applications, we show that Low 1 is parameter definable, and we provide methods that lead to a new example of a ∅-definable ideal. Moreover, we prove that (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  12.  32
    Lowness Properties and Approximations of the Jump.Santiago Figueira, André Nies & Frank Stephan - 2008 - Annals of Pure and Applied Logic 152 (1):51-66.
    We study and compare two combinatorial lowness notions: strong jump-traceability and well-approximability of the jump, by strengthening the notion of jump-traceability and super-lowness for sets of natural numbers. A computable non-decreasing unbounded function h is called an order function. Informally, a set A is strongly jump-traceable if for each order function h, for each input e one may effectively enumerate a set Te of possible values for the jump JA, and the number of values enumerated is at most h. A′ (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  13. Definability in the Recursively Enumerable Degrees.André Nies, Richard A. Shore & Theodore A. Slaman - 1996 - Bulletin of Symbolic Logic 2 (4):392-404.
  14.  20
    Recursively Enumerable Equivalence Relations Modulo Finite Differences.André Nies - 1994 - Mathematical Logic Quarterly 40 (4):490-518.
    We investigate the upper semilattice Eq* of recursively enumerable equivalence relations modulo finite differences. Several natural subclasses are shown to be first-order definable in Eq*. Building on this we define a copy of the structure of recursively enumerable many-one degrees in Eq*, thereby showing that Th has the same computational complexity as the true first-order arithmetic.
    Direct download  
     
    Export citation  
     
    Bookmark   4 citations  
  15.  9
    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 below all superlow Martin-Löf random sets is strongly (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  16.  16
    Finite Automata Presentable Abelian Groups.André Nies & Pavel Semukhin - 2010 - Annals of Pure and Applied Logic 161 (3):458-467.
    We give new examples of FA presentable torsion-free abelian groups. Namely, for every n2, we construct a rank n indecomposable torsion-free abelian group which has an FA presentation. We also construct an FA presentation of the group in which every nontrivial cyclic subgroup is not FA recognizable.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  17. Structural Properties and Σ20 Enumeration Degrees.André Nies & Andrea Sorbi - 2000 - Journal of Symbolic Logic 65 (1):285-292.
    We prove that each Σ 0 2 set which is hypersimple relative to $\emptyset$ ' is noncuppable in the structure of the Σ 0 2 enumeration degrees. This gives a connection between properties of Σ 0 2 sets under inclusion and and the Σ 0 2 enumeration degrees. We also prove that some low non-computably enumerable enumeration degree contains no set which is simple relative to $\emptyset$ '.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  18.  8
    Interpreting True Arithmetic in the Theory of the R.E. Truth Table Degrees.André Nies & Richard A. Shore - 1995 - Annals of Pure and Applied Logic 75 (3):269-311.
    We show that the elementary theory of the recursively enumerable tt-degrees has the same computational complexity as true first-order arithmetic. As auxiliary results, we prove theorems about exact pairs and initial segments in the tt-degrees.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  19.  72
    Lowness and Π₂⁰ Nullsets.Rod Downey, Andre Nies, Rebecca Weber & Liang Yu - 2006 - Journal of Symbolic Logic 71 (3):1044-1052.
    We prove that there exists a noncomputable c.e. real which is low for weak 2-randomness, a definition of randomness due to Kurtz, and that all reals which are low for weak 2-randomness are low for Martin-Löf randomness.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  20.  46
    Randomness and Computability: Open Questions.Joseph S. Miller & André Nies - 2006 - Bulletin of Symbolic Logic 12 (3):390-410.
  21.  15
    Interpreting N in the Computably Enumerable Weak Truth Table Degrees.André Nies - 2001 - Annals of Pure and Applied Logic 107 (1-3):35-48.
    We give a first-order coding without parameters of a copy of in the computably enumerable weak truth table degrees. As a tool, we develop a theory of parameter definable subsets.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  22.  32
    Benign Cost Functions and Lowness Properties.Noam Greenberg & André Nies - 2011 - Journal of Symbolic Logic 76 (1):289 - 312.
    We show that the class of strongly jump-traceable c.e. sets can be characterised as those which have sufficiently slow enumerations so they obey a class of well-behaved cost functions, called benign. This characterisation implies the containment of the class of strongly jump-traceable c.e. Turing degrees in a number of lowness classes, in particular the classes of the degrees which lie below incomplete random degrees, indeed all LR-hard random degrees, and all ω-c.e. random degrees. The last result implies recent results of (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  23.  10
    Randomness Notions and Reverse Mathematics.André Nies & Paul Shafer - 2020 - Journal of Symbolic Logic 85 (1):271-299.
    We investigate the strength of a randomness notion ${\cal R}$ as a set-existence principle in second-order arithmetic: for each Z there is an X that is ${\cal R}$-random relative to Z. We show that the equivalence between 2-randomness and being infinitely often C-incompressible is provable in $RC{A_0}$. We verify that $RC{A_0}$ proves the basic implications among randomness notions: 2-random $\Rightarrow$ weakly 2-random $\Rightarrow$ Martin-Löf random $\Rightarrow$ computably random $\Rightarrow$ Schnorr random. Also, over $RC{A_0}$ the existence of computable randoms is equivalent (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  24.  38
    The Theory of the Recursively Enumerable Weak Truth-Table Degrees is Undecidable.Klaus Ambos-Spies, André Nies & Richard A. Shore - 1992 - Journal of Symbolic Logic 57 (3):864-874.
    We show that the partial order of Σ0 3-sets under inclusion is elementarily definable with parameters in the semilattice of r.e. wtt-degrees. Using a result of E. Herrmann, we can deduce that this semilattice has an undecidable theory, thereby solving an open problem of P. Odifreddi.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  25.  33
    Upper Bounds on Ideals in the Computably Enumerable Turing Degrees.George Barmpalias & André Nies - 2011 - Annals of Pure and Applied Logic 162 (6):465-473.
    We study ideals in the computably enumerable Turing degrees, and their upper bounds. Every proper ideal in the c.e. Turing degrees has an incomplete upper bound. It follows that there is no prime ideal in the c.e. Turing degrees. This answers a question of Calhoun [2]. Every proper ideal in the c.e. Turing degrees has a low2 upper bound. Furthermore, the partial order of ideals under inclusion is dense.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  26.  33
    Demuth Randomness and Computational Complexity.Antonín Kučera & André Nies - 2011 - Annals of Pure and Applied Logic 162 (7):504-513.
    Demuth tests generalize Martin-Löf tests in that one can exchange the m-th component a computably bounded number of times. A set fails a Demuth test if Z is in infinitely many final versions of the Gm. If we only allow Demuth tests such that GmGm+1 for each m, we have weak Demuth randomness.We show that a weakly Demuth random set can be high and , yet not superhigh. Next, any c.e. set Turing below a Demuth random set is strongly jump-traceable.We (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  27. Higher Kurtz Randomness.Bjørn Kjos-Hanssen, André Nies, Frank Stephan & Liang Yu - 2010 - Annals of Pure and Applied Logic 161 (10):1280-1290.
    A real x is -Kurtz random if it is in no closed null set . We show that there is a cone of -Kurtz random hyperdegrees. We characterize lowness for -Kurtz randomness as being -dominated and -semi-traceable.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  28.  2
    The Reverse Mathematics of Theorems of Jordan and Lebesgue.André Nies, Marcus A. Triplett & Keita Yokoyama - 2021 - Journal of Symbolic Logic 86 (4):1657-1675.
    The Jordan decomposition theorem states that every function $f \colon \, [0,1] \to \mathbb {R}$ of bounded variation can be written as the difference of two non-decreasing functions. Combining this fact with a result of Lebesgue, every function of bounded variation is differentiable almost everywhere in the sense of Lebesgue measure. We analyze the strength of these theorems in the setting of reverse mathematics. Over $\mathsf {RCA}_{0}$, a stronger version of Jordan’s result where all functions are continuous is equivalent to (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  29.  14
    Cappable Recursively Enumerable Degrees and Post's Program.Klaus Ambos-Spies & André Nies - 1992 - Archive for Mathematical Logic 32 (1):51-56.
    We give a simple structural property which characterizes the r.e. sets whose (Turing) degrees are cappable. Since cappable degrees are incomplete, this may be viewed as a solution of Post's program, which asks for a simple structural property of nonrecursive r.e. sets which ensures incompleteness.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  30.  66
    Calibrating Randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
    We report on some recent work centered on attempts to understand when one set is more random than another. We look at various methods of calibration by initial segment complexity, such as those introduced by Solovay [125], Downey, Hirschfeldt, and Nies [39], Downey, Hirschfeldt, and LaForte [36], and Downey [31]; as well as other methods such as lowness notions of Kučera and Terwijn [71], Terwijn and Zambella [133], Nies [101, 100], and Downey, Griffiths, and Reid [34]; higher level (...)
    Direct download (11 more)  
     
    Export citation  
     
    Bookmark   28 citations  
  31.  17
    Demuth’s Path to Randomness.Antonín Kučera, André Nies & Christopher P. Porter - 2015 - Bulletin of Symbolic Logic 21 (3):270-305.
    Osvald Demuth studied constructive analysis from the viewpoint of the Russian school of constructive mathematics. In the course of his work he introduced various notions of effective null set which, when phrased in classical language, yield a number of major algorithmic randomness notions. In addition, he proved several results connecting constructive analysis and randomness that were rediscovered only much later.In this paper, we trace the path that took Demuth from his constructivist roots to his deep and innovative work on the (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  32. Program Size Complexity for Possibly Infinite Computations.Verónica Becher, Santiago Figueira, André Nies & Silvana Picchi - 2005 - Notre Dame Journal of Formal Logic 46 (1):51-64.
    We define a program size complexity function $H^\infty$ as a variant of the prefix-free Kolmogorov complexity, based on Turing monotone machines performing possibly unending computations. We consider definitions of randomness and triviality for sequences in ${\{0,1\}}^\omega$ relative to the $H^\infty$ complexity. We prove that the classes of Martin-Löf random sequences and $H^\infty$-random sequences coincide and that the $H^\infty$-trivial sequences are exactly the recursive ones. We also study some properties of $H^\infty$ and compare it with other complexity functions. In particular, $H^\infty$ (...)
    Direct download (11 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  33.  36
    Initial Segments of the Lattice of Π10 Classes.Douglas Cenzer & Andre Nies - 2001 - Journal of Symbolic Logic 66 (4):1749-1765.
    We show that in the lattice E Π of Π 0 1 classes there are initial segments [ $\emptyset$ , P] = L(P) which are not Boolean algebras, but which have a decidable theory. In fact, we will construct for any finite distributive lattice L which satisfies the dual of the usual reduction property a Π 0 1 class P such that L is isomorphic to the lattice L(P)*, which is L(P), modulo finite differences. For the 2-element lattice, we obtain (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  34.  10
    Borel Structures and Borel Theories.Greg Hjorth & André Nies - 2011 - Journal of Symbolic Logic 76 (2):461 - 476.
    We show that there is a complete, consistent Borel theory which has no "Borel model" in the following strong sense: There is no structure satisfying the theory for which the elements of the structure are equivalence classes under some Borel equivalence relation and the interpretations of the relations and function symbols are uniformly Borel. We also investigate Borel isomorphisms between Borel structures.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  35.  11
    The Complexity of Topological Group Isomorphism.Alexander S. Kechris, André Nies & Katrin Tent - 2018 - Journal of Symbolic Logic 83 (3):1190-1203.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  36.  42
    The Undecidability of the II4 Theory for the R. E. Wtt and Turing Degrees.Steffen Lempp & André Nies - 1995 - Journal of Symbolic Logic 60 (4):1118 - 1136.
    We show that the Π 4 -theory of the partial order of recursively enumerable weak truth-table degrees is undecidable, and give a new proof of the similar fact for r.e. T-degrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  37.  38
    The Undecidability of the II$^_4$ Theory for the R. E. Wtt and Turing Degrees.Steffen Lempp & André Nies - 1995 - Journal of Symbolic Logic 60 (4):1118-1136.
    We show that the $\Pi_4$-theory of the partial order of recursively enumerable weak truth-table degrees is undecidable, and give a new proof of the similar fact for r.e. T-degrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  38. Notre Dame, Indiana May 20–May 23, 2009.Patricia Blanchette, Heike Mildenberger, André Nies, Anand Pillay, Alexander Razborov, Alexandra Shlapentokh, John R. Steel & Boris Zilber - 2009 - Bulletin of Symbolic Logic 15 (4).
     
    Export citation  
     
    Bookmark  
  39.  4
    Using Almost-Everywhere Theorems From Analysis to Study Randomness.Kenshi Miyabe, André Nies & Jing Zhang - 2016 - Bulletin of Symbolic Logic 22 (3):305-331.
    We study algorithmic randomness notions via effective versions of almost-everywhere theorems from analysis and ergodic theory. The effectivization is in terms of objects described by a computably enumerable set, such as lower semicomputable functions. The corresponding randomness notions are slightly stronger than Martin–Löf randomness.We establish several equivalences. Given a ML-random realz, the additional randomness strengths needed for the following are equivalent.all effectively closed classes containingzhave density 1 atz.all nondecreasing functions with uniformly left-c.e. increments are differentiable atz.zis a Lebesgue point of (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  40. Liang," Lowness and Π20 Nullsets".Rod& Nies Downey, André Weber & Rebecca Yu - 2006 - Journal of Symbolic Logic 71:3.
     
    Export citation  
     
    Bookmark  
  41.  1
    Fraïssé Limits for Relational Metric Structures.David Bryant, André Nies & Paul Tupper - 2021 - Journal of Symbolic Logic 86 (3):913-934.
    The general theory developed by Ben Yaacov for metric structures provides Fraïssé limits which are approximately ultrahomogeneous. We show here that this result can be strengthened in the case of relational metric structures. We give an extra condition that guarantees exact ultrahomogenous limits. The condition is quite general. We apply it to stochastic processes, the class of diversities, and its subclass of $L_1$ diversities.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  42. 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   1 citation  
  43.  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  
  44.  15
    Relativizing Chaitin's Halting Probability.Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller & André Nies - 2005 - Journal of Mathematical Logic 5 (02):167-192.
    As a natural example of a 1-random real, Chaitin proposed the halting probability Ω of a universal prefix-free machine. We can relativize this example by considering a universal prefix-free oracle machine U. Let [Formula: see text] be the halting probability of UA; this gives a natural uniform way of producing an A-random real for every A ∈ 2ω. It is this operator which is our primary object of study. We can draw an analogy between the jump operator from computability theory (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   18 citations  
  45.  4
    Muchnik Degrees and Cardinal Characteristics.Benoit Monin & André Nies - 2021 - Journal of Symbolic Logic 86 (2):471-498.
    A mass problem is a set of functions $\omega \to \omega $. For mass problems ${\mathcal {C}}, {\mathcal {D}}$, one says that ${\mathcal {C}}$ is Muchnik reducible to ${\mathcal {D}}$ if each function in ${\mathcal {C}}$ is computed by a function in ${\mathcal {D}}$. In this paper we study some highness properties of Turing oracles, which we view as mass problems. We compare them with respect to Muchnik reducibility and its uniform strengthening, Medvedev reducibility.For $p \in [0,1]$ let ${\mathcal {D}}$ (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  46.  8
    Denjoy, Demuth and Density.Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller & André Nies - 2014 - Journal of Mathematical Logic 14 (1):1450004.
    We consider effective versions of two classical theorems, the Lebesgue density theorem and the Denjoy–Young–Saks theorem. For the first, we show that a Martin-Löf random real z ∈ [0, 1] is Turing incomplete if and only if every effectively closed class.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  47.  23
    Kolmogorov–Loveland Randomness and Stochasticity.Wolfgang Merkle, Joseph S. Miller, André Nies, Jan Reimann & Frank Stephan - 2006 - Annals of Pure and Applied Logic 138 (1):183-210.
    An infinite binary sequence X is Kolmogorov–Loveland random if there is no computable non-monotonic betting strategy that succeeds on X in the sense of having an unbounded gain in the limit while betting successively on bits of X. A sequence X is KL-stochastic if there is no computable non-monotonic selection rule that selects from X an infinite, biased sequence.One of the major open problems in the field of effective randomness is whether Martin-Löf randomness is the same as KL-randomness. Our first (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  48.  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  
  49.  19
    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.
    We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relationsR,S, a componentwise reducibility is defined byR≤S⇔ ∃f∀x, y[x R y↔fS f].Here,fis taken from a suitable class of effective functions. For us the relations will be on natural numbers, andfmust be computable. We show that there is a${\rm{\Pi }}_1^0$-complete equivalence relation, but no${\rm{\Pi }}_k^0$-complete fork≥ 2. We show that${\rm{\Sigma }}_k^0$preorders arising naturally in the above-mentioned areas are${\rm{\Sigma }}_k^0$-complete. This includes polynomial timem-reducibility on (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  50.  7
    Isaac Newton Institute, Cambridge, UK July 2–6, 2012.George Barmpalias, Vasco Brattka, Adam Day, Rod Downey, John Hitchcock, Michal Koucký, Andy Lewis, Jack Lutz, André Nies & Alexander Shen - 2013 - Bulletin of Symbolic Logic 19 (1).
    Direct download  
     
    Export citation  
     
    Bookmark  
1 — 50 / 1000