17 found
Order:
  1.  61
    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 randomness notions (...)
    Direct download (11 more)  
     
    Export citation  
     
    Bookmark   25 citations  
  2.  82
    Computational Randomness and Lowness.Sebastiaan A. Terwijn & Domenico Zambella - 2001 - Journal of Symbolic Logic 66 (3):1199-1205.
    We prove that there are uncountably many sets that are low for the class of Schnorr random reals. We give a purely recursion theoretic characterization of these sets and show that they all have Turing degree incomparable to 0'. This contrasts with a result of Kučera and Terwijn [5] on sets that are low for the class of Martin-Löf random reals.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   17 citations  
  3.  24
    The Medvedev Lattice of Computably Closed Sets.Sebastiaan A. Terwijn - 2006 - Archive for Mathematical Logic 45 (2):179-190.
    Simpson introduced the lattice of Π0 1 classes under Medvedev reducibility. Questions regarding completeness in are related to questions about measure and randomness. We present a solution to a question of Simpson about Medvedev degrees of Π0 1 classes of positive measure that was independently solved by Simpson and Slaman. We then proceed to discuss connections to constructive logic. In particular we show that the dual of does not allow an implication operator (i.e. that is not a Heyting algebra). We (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  4.  7
    Generalizations of the Recursion Theorem.Sebastiaan A. Terwijn - 2018 - Journal of Symbolic Logic 83 (4):1683-1690.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  11
    Intermediate Logics and Factors of the Medvedev Lattice.Andrea Sorbi & Sebastiaan A. Terwijn - 2008 - Annals of Pure and Applied Logic 155 (2):69-85.
    We investigate the initial segments of the Medvedev lattice as Brouwer algebras, and study the propositional logics connected to them.
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  6.  8
    On Partial Randomness.Cristian S. Calude, Ludwig Staiger & Sebastiaan A. Terwijn - 2006 - Annals of Pure and Applied Logic 138 (1):20-30.
    If is a random sequence, then the sequence is clearly not random; however, seems to be “about half random”. L. Staiger [Kolmogorov complexity and Hausdorff dimension, Inform. and Comput. 103 159–194 and A tight upper bound on Kolmogorov complexity and uniformly optimal prediction, Theory Comput. Syst. 31 215–229] and K. Tadaki [A generalisation of Chaitin’s halting probability Ω and halting self-similar sets, Hokkaido Math. J. 31 219–253] have studied the degree of randomness of sequences or reals by measuring their “degree (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  7.  20
    Lowness for the Class of Random Sets.Antonín Kučera & Sebastiaan A. Terwijn - 1999 - Journal of Symbolic Logic 64 (4):1396-1402.
    A positive answer to a question of M. van Lambalgen and D. Zambella whether there exist nonrecursive sets that are low for the class of random sets is obtained. Here a set A is low for the class RAND of random sets if RAND = RAND A.
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  8.  29
    Constructive Logic and the Medvedev Lattice.Sebastiaan A. Terwijn - 2006 - Notre Dame Journal of Formal Logic 47 (1):73-82.
    We study the connection between factors of the Medvedev lattice and constructive logic. The algebraic properties of these factors determine logics lying in between intuitionistic propositional logic and the logic of the weak law of the excluded middle (also known as De Morgan, or Jankov, logic). We discuss the relation between the weak law of the excluded middle and the algebraic notion of join-reducibility. Finally we discuss autoreducible degrees.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  9.  26
    Model Theory of Measure Spaces and Probability Logic.Rutger Kuyper & Sebastiaan A. Terwijn - 2013 - Review of Symbolic Logic 6 (3):367-393.
    We study the model-theoretic aspects of a probability logic suited for talking about measure spaces. This nonclassical logic has a model theory rather different from that of classical predicate logic. In general, not every satisfiable set of sentences has a countable model, but we show that one can always build a model on the unit interval. Also, the probability logic under consideration is not compact. However, using ultraproducts we can prove a compactness theorem for a certain class of weak models.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  10.  10
    On the Structure of the Medvedev Lattice.Sebastiaan A. Terwijn - 2008 - Journal of Symbolic Logic 73 (2):543 - 558.
    We investigate the structure of the Medvedev lattice as a partial order. We prove that every interval in the lattice is either finite, in which case it is isomorphic to a finite Boolean algebra, or contains an antichain of size $2^{2^{\aleph }0}$ , the size of the lattice itself. We also prove that it is consistent with ZFC that the lattice has chains of size $2^{2^{\aleph }0}$ , and in fact these big chains occur in every infinite interval. We also (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  11.  22
    Generalizations of the Weak Law of the Excluded Middle.Andrea Sorbi & Sebastiaan A. Terwijn - 2015 - Notre Dame Journal of Formal Logic 56 (2):321-331.
    We study a class of formulas generalizing the weak law of the excluded middle and provide a characterization of these formulas in terms of Kripke frames and Brouwer algebras. We use these formulas to separate logics corresponding to factors of the Medvedev lattice.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  12.  29
    Kripke Models, Distributive Lattices, and Medvedev Degrees.Sebastiaan A. Terwijn - 2007 - Studia Logica 85 (3):319-332.
    We define a variant of the standard Kripke semantics for intuitionistic logic, motivated by the connection between constructive logic and the Medvedev lattice. We show that while the new semantics is still complete, it gives a simple and direct correspondence between Kripke models and algebraic structures such as factors of the Medvedev lattice.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  13.  4
    Fixed Point Theorems for Precomplete Numberings.Henk Barendregt & Sebastiaan A. Terwijn - 2019 - Annals of Pure and Applied Logic 170 (10):1151-1161.
    In the context of his theory of numberings, Ershov showed that Kleene's recursion theorem holds for any precomplete numbering. We discuss various generalizations of this result. Among other things, we show that Arslanov's completeness criterion also holds for every precomplete numbering, and we discuss the relation with Visser's ADN theorem, as well as the uniformity or nonuniformity of the various fixed point theorems. Finally, we base numberings on partial combinatory algebras and prove a generalization of Ershov's theorem in this context.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14.  1
    The noneffectivity of Arslanov’s completeness criterion and related theorems.Sebastiaan A. Terwijn - 2020 - Archive for Mathematical Logic 59 (5):703-713.
    We discuss the effectivity of Arslanov’s completeness criterion. In particular, we show that a parameterized version, similar to the recursion theorem with parameters, fails. We also discuss the effectivity of another extension of the recursion theorem, namely Visser’s ADN theorem, as well as that of a joint generalization of the ADN theorem and Arslanov’s completeness criterion.
    No categories
    Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  15.  11
    Covering the Recursive Sets.Bjørn Kjos-Hanssen, Frank Stephan & Sebastiaan A. Terwijn - 2017 - Annals of Pure and Applied Logic 168 (4):804-823.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  16.  17
    Arithmetical Measure.Sebastiaan A. Terwijn & Leen Torenvliet - 1998 - Mathematical Logic Quarterly 44 (2):277-286.
    We develop arithmetical measure theory along the lines of Lutz [10]. This yields the same notion of measure 0 set as considered before by Martin-Löf, Schnorr, and others. We prove that the class of sets constructible by r.e.-constructors, a direct analogue of the classes Lutz devised his resource bounded measures for in [10], is not equal to RE, the class of r.e. sets, and we locate this class exactly in terms of the common recursion-theoretic reducibilities below K. We note that (...)
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  17.  60
    Randomness, Relativization and Turing Degrees.André Nies, Frank Stephan & Sebastiaan A. Terwijn - 2005 - Journal of Symbolic Logic 70 (2):515-535.
    We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is Martin-Löf random relative to ∅. We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C ≥ |x|-c. The ‘only if' direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity. Next we prove some results (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   16 citations