Switch to: References

Add citations

You must login to add citations.
  1. Lowness for Isomorphism, Countable Ideals, and Computable Traceability.Johanna N. Y. Franklin & Reed Solomon - 2020 - Mathematical Logic Quarterly 66 (1):104-114.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  • Quasi‐Completeness and Functions Without Fixed‐Points.Ilnur I. Batyrshin - 2006 - Mathematical Logic Quarterly 52 (6):595-601.
    We prove a completeness criterion for quasi-reducibility and generalize it to higher levels of the arithmetical hierarchy. As an application of the criterion we obtain Q-completeness of the set of all pairs such that the prefix-free Kolmogorov complexity of x is less than n.
    Direct download  
     
    Export citation  
     
    Bookmark  
  • A Survey of Mučnik and Medvedev Degrees.Peter G. Hinman - 2012 - Bulletin of Symbolic Logic 18 (2):161-229.
    We survey the theory of Mucnik and Medvedev degrees of subsets of $^{\omega}{\omega}$with particular attention to the degrees of $\Pi_{1}^{0}$ subsets of $^{\omega}2$. Sections 1-6 present the major definitions and results in a uniform notation. Sections 7-6 present proofs, some more complete than others, of the major results of the subject together with much of the required background material.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  • Ramsey-Type Graph Coloring and Diagonal Non-Computability.Ludovic Patey - 2015 - Archive for Mathematical Logic 54 (7-8):899-914.
    A function is diagonally non-computable if it diagonalizes against the universal partial computable function. D.n.c. functions play a central role in algorithmic randomness and reverse mathematics. Flood and Towsner asked for which functions h, the principle stating the existence of an h-bounded d.n.c. function implies Ramsey-type weak König’s lemma. In this paper, we prove that for every computable order h, there exists an ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\omega}$$\end{document} -model of h-DNR which is not a not (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Immunity and Hyperimmunity for Sets of Minimal Indices.Frank Stephan & Jason Teutsch - 2008 - Notre Dame Journal of Formal Logic 49 (2):107-125.
    We extend Meyer's 1972 investigation of sets of minimal indices. Blum showed that minimal index sets are immune, and we show that they are also immune against high levels of the arithmetic hierarchy. We give optimal immunity results for sets of minimal indices with respect to the arithmetic hierarchy, and we illustrate with an intuitive example that immunity is not simply a refinement of arithmetic complexity. Of particular note here are the fact that there are three minimal index sets located (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • 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)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  • 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   3 citations  
  • 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   28 citations  
  • < I> Σ_< Sub> 5-Completeness of Index Sets Arising From the Recursively Enumerable Turing Degrees.Michael A. Jahn - 1996 - Annals of Pure and Applied Logic 79 (2):109-137.
    We employ techniques related to Lempp and Lerman's “iterated trees of strategies” to directly measure a Σ5-predicate and use this in showing the index set of the cuppable r.e. sets to be Σ5-complete. We also show how certain technical devices arise naturally out of the iterated-trees context, in particular, links arise as manifestations of a generalized notion of “stage”.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  • ∑5-Completeness of Index Sets Arising From the Lattice of Recursively Enumerable Sets.Michael A. Jahn - 1996 - Annals of Pure and Applied Logic 80 (1):55-67.
    We extend the techniques of Jahn to show the index set of the major subsets to be ∑5-complete. This was a question left open in Lempp and its solution involves a level-4 construction. We also show how the measuring of e-states arises naturally out of our iterated-trees approach to breaking up requirements.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Open Questions About Ramsey-Type Statements in Reverse Mathematics.Ludovic Patey - 2016 - Bulletin of Symbolic Logic 22 (2):151-169.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • The D.R.E. Degrees Are Not Dense.S. Barry Cooper, Leo Harrington, Alistair H. Lachlan, Steffen Lempp & Robert I. Soare - 1991 - Annals of Pure and Applied Logic 55 (2):125-151.
    By constructing a maximal incomplete d.r.e. degree, the nondensity of the partial order of the d.r.e. degrees is established. An easy modification yields the nondensity of the n-r.e. degrees and of the ω-r.e. degrees.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   29 citations  
  • Σ5-Completeness of Index Sets Arising From the Recursively Enumerable Turing Degrees.Michael A. Jahn - 1996 - Annals of Pure and Applied Logic 79 (2):109-137.
    We employ techniques related to Lempp and Lerman's “iterated trees of strategies” to directly measure a Σ5-predicate and use this in showing the index set of the cuppable r.e. sets to be Σ5-complete. We also show how certain technical devices arise naturally out of the iterated-trees context, in particular, links arise as manifestations of a generalized notion of “stage”.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  • On Relative Randomness.Antonín Kučera - 1993 - Annals of Pure and Applied Logic 63 (1):61-67.
    Kuera, A., On relative randomness, Annals of Pure and Applied Logic 63 61–67. It is the aim of the paper to answer a question raised by M. van Lambalgen and D. Zambella whether there can be a nonrecursive set A having the property that there is a set B such that B is 1-random relative to A and simultaneously A is recursive in B. We give apositive answer to this question as well as further information about relative randomness.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  • On the Turing Degrees of Minimal Index Sets.Jason Teutsch - 2007 - Annals of Pure and Applied Logic 148 (1):63-80.
    We study generalizations of shortest programs as they pertain to Schaefer’s problem. We identify sets of -minimal and -minimal indices and characterize their truth-table and Turing degrees. In particular, we show , , and that there exists a Kolmogorov numbering ψ satisfying both and . This Kolmogorov numbering also achieves maximal truth-table degree for other sets of minimal indices. Finally, we show that the set of shortest descriptions, , is 2-c.e. but not co-2-c.e. Some open problems are left for the (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Coding True Arithmetic in the Medvedev Degrees of Classes.Paul Shafer - 2012 - Annals of Pure and Applied Logic 163 (3):321-337.
  • Extending and Interpreting Post’s Programme.S. Barry Cooper - 2010 - Annals of Pure and Applied Logic 161 (6):775-788.
    Computability theory concerns information with a causal–typically algorithmic–structure. As such, it provides a schematic analysis of many naturally occurring situations. Emil Post was the first to focus on the close relationship between information, coded as real numbers, and its algorithmic infrastructure. Having characterised the close connection between the quantifier type of a real and the Turing jump operation, he looked for more subtle ways in which information entails a particular causal context. Specifically, he wanted to find simple relations on reals (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark