17 found
Order:
  1. 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   29 citations  
  2.  24
    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   5 citations  
  3.  20
    Generalizations of the recursion theorem.Sebastiaan A. Terwijn - 2018 - Journal of Symbolic Logic 83 (4):1683-1690.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  4.  41
    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 (3 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  5.  48
    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 (9 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  6.  18
    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   7 citations  
  7.  47
    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   6 citations  
  8.  15
    Ordinal analysis of partial combinatory algebras.Paul Shafer & Sebastiaan A. Terwijn - 2021 - Journal of Symbolic Logic 86 (3):1154-1188.
    For every partial combinatory algebra, we define a hierarchy of extensionality relations using ordinals. We investigate the closure ordinals of pca’s, i.e., the smallest ordinals where these relations become equal. We show that the closure ordinal of Kleene’s first model is ${\omega _1^{\textit {CK}}}$ and that the closure ordinal of Kleene’s second model is $\omega _1$. We calculate the exact complexities of the extensionality relations in Kleene’s first model, showing that they exhaust the hyperarithmetical hierarchy. We also discuss embeddings of (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  9.  43
    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 (9 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  10.  49
    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  
  11.  26
    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   2 citations  
  12.  49
    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  
  13.  17
    Embeddings between Partial Combinatory Algebras.Anton Golov & Sebastiaan A. Terwijn - 2023 - Notre Dame Journal of Formal Logic 64 (1):129-158.
    Partial combinatory algebras (pcas) are algebraic structures that serve as generalized models of computation. In this article, we study embeddings of pcas. In particular, we systematize the embeddings between relativizations of Kleene’s models, of van Oosten’s sequential computation model, and of Scott’s graph model, showing that an embedding between two relativized models exists if and only if there exists a particular reduction between the oracles. We obtain a similar result for the lambda calculus, showing in particular that it cannot be (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14.  25
    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  
  15.  30
    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  
     
    Export citation  
     
    Bookmark  
  16.  21
    Computability in partial combinatory algebras.Sebastiaan A. Terwijn - 2020 - Bulletin of Symbolic Logic 26 (3-4):224-240.
    We prove a number of elementary facts about computability in partial combinatory algebras. We disprove a suggestion made by Kreisel about using Friedberg numberings to construct extensional pca’s. We then discuss separability and elements without total extensions. We relate this to Ershov’s notion of precompleteness, and we show that precomplete numberings are not 1–1 in general.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  17.  12
    The noneffectivity of Arslanov’s completeness criterion and related theorems.Sebastiaan A. Terwijn - 2020 - Archive for Mathematical Logic 59 (5-6):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)  
     
    Export citation  
     
    Bookmark