18 found
Order:
See also
Bjørn Kjos-Hanssen
University of Hawaii
  1. On a Conjecture of Dobrinen and Simpson Concerning Almost Everywhere Domination.Stephen Binns, Bjørn Kjos-Hanssen, Manuel Lerman & Reed Solomon - 2006 - Journal of Symbolic Logic 71 (1):119 - 136.
  2.  71
    Only Human: A Book Review of The Turing Guide. [REVIEW]Bjørn Kjos-Hanssen - forthcoming - Notices of the American Mathematical Society 66 (4).
    This is a review of The Turing Guide (2017), written by Jack Copeland, Jonathan Bowen, Mark Sprevak, Robin Wilson, and others. The review includes a new sociological approach to the problem of computability in physics.
    Direct download  
     
    Export citation  
     
    Bookmark  
  3. Martin-Löf Randomness and Galton–Watson Processes.David Diamondstone & Bjørn Kjos-Hanssen - 2012 - Annals of Pure and Applied Logic 163 (5):519-529.
  4. 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   1 citation  
  5.  27
    Local Initial Segments of the Turing Degrees.Bjørn Kjos-Hanssen - 2003 - Bulletin of Symbolic Logic 9 (1):26-36.
    Recent results on initial segments of the Turing degrees are presented, and some conjectures about initial segments that have implications for the existence of nontrivial automorphisms of the Turing degrees are indicated.
    Direct download (14 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  6.  20
    Self-Embeddings of Computable Trees.Stephen Binns, Bjørn Kjos-Hanssen, Manuel Lerman, James H. Schmerl & Reed Solomon - 2008 - Notre Dame Journal of Formal Logic 49 (1):1-37.
    We divide the class of infinite computable trees into three types. For the first and second types, 0' computes a nontrivial self-embedding while for the third type 0'' computes a nontrivial self-embedding. These results are optimal and we obtain partial results concerning the complexity of nontrivial self-embeddings of infinite computable trees considered up to isomorphism. We show that every infinite computable tree must have either an infinite computable chain or an infinite Π01 antichain. This result is optimal and has connections (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  7.  17
    Finding Paths Through Narrow and Wide Trees.Stephen Binns & Bjørn Kjos-Hanssen - 2009 - Journal of Symbolic Logic 74 (1):349-360.
    We consider two axioms of second-order arithmetic. These axioms assert, in two different ways, that infinite but narrow binary trees always have infinite paths. We show that both axioms are strictly weaker than Weak König's Lemma, and incomparable in strength to the dual statement (WWKL) that wide binary trees have paths.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  8.  32
    Comparing DNR and WWKL.Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp & Theodore A. Slaman - 2004 - Journal of Symbolic Logic 69 (4):1089-1104.
    In Reverse Mathematics, the axiom system DNR, asserting the existence of diagonally non-recursive functions, is strictly weaker than WWKL0.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  9.  32
    Superhighness.Bjørn Kjos-Hanssen & Andrée Nies - 2009 - Notre Dame Journal of Formal Logic 50 (4):445-452.
    We prove that superhigh sets can be jump traceable, answering a question of Cole and Simpson. On the other hand, we show that such sets cannot be weakly 2-random. We also study the class $superhigh^\diamond$ and show that it contains some, but not all, of the noncomputable K-trivial sets.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  10.  12
    How Much Randomness is Needed for Statistics?Bjørn Kjos-Hanssen, Antoine Taveneaux & Neil Thapen - 2012 - In S. Barry Cooper (ed.), Annals of Pure and Applied Logic. pp. 395--404.
    In algorithmic randomness, when one wants to define a randomness notion with respect to some non-computable measure λ, a choice needs to be made. One approach is to allow randomness tests to access the measure λ as an oracle . The other approach is the opposite one, where the randomness tests are completely effective and do not have access to the information contained in λ . While the Hippocratic approach is in general much more restrictive, there are cases where the (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  11.  21
    Lattice Initial Segments of the Hyperdegrees.Richard A. Shore & Bjørn Kjos-Hanssen - 2010 - Journal of Symbolic Logic 75 (1):103-130.
    We affirm a conjecture of Sacks [1972] by showing that every countable distributive lattice is isomorphic to an initial segment of the hyperdegrees, $\scr{D}_{h}$ . In fact, we prove that every sublattice of any hyperarithmetic lattice (and so, in particular, every countable, locally finite lattice) is isomorphic to an initial segment of $\scr{D}_{h}$ . Corollaries include the decidability of the two quantifier theory of $\scr{D}_{h}$ and the undecidability of its three quantifier theory. The key tool in the proof is a (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  12.  10
    Permutations of the Integers Induce Only the Trivial Automorphism of the Turing Degrees.Bjørn Kjos-Hanssen - 2018 - Bulletin of Symbolic Logic 24 (2):165-174.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  13.  41
    A Strong Law of Computationally Weak Subsets.Bjørn Kjos-Hanssen - 2011 - Journal of Mathematical Logic 11 (1):1-10.
    We show that in the setting of fair-coin measure on the power set of the natural numbers, each sufficiently random set has an infinite subset that computes no random set. That is, there is an almost sure event [Formula: see text] such that if [Formula: see text] then X has an infinite subset Y such that no element of [Formula: see text] is Turing computable from Y.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark  
  14.  10
    The Strength of the Grätzer-Schmidt Theorem.Katie Brodhead, Mushfeq Khan, Bjørn Kjos-Hanssen, William A. Lampe, Paul Kim Long V. Nguyen & Richard A. Shore - 2016 - Archive for Mathematical Logic 55 (5-6):687-704.
    The Grätzer-Schmidt theorem of lattice theory states that each algebraic lattice is isomorphic to the congruence lattice of an algebra. We study the reverse mathematics of this theorem. We also show thatthe set of indices of computable lattices that are complete is Π11\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi ^1_1$$\end{document}-complete;the set of indices of computable lattices that are algebraic is Π11\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi ^1_1$$\end{document}-complete;the set of compact elements of a computable (...)
    No categories
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  15.  18
    Conference on Computability, Complexity and Randomness.Verónica Becher, C. T. Chong, Rod Downey, Noam Greenberg, Antonin Kucera, Bjørn Kjos-Hanssen, Steffen Lempp, Antonio Montalbán, Jan Reimann & Stephen Simpson - 2008 - Bulletin of Symbolic Logic 14 (4):548-549.
  16.  12
    How Much Randomness is Needed for Statistics?Bjørn Kjos-Hanssen, Antoine Taveneaux & Neil Thapen - 2014 - Annals of Pure and Applied Logic 165 (9):1470-1483.
    In algorithmic randomness, when one wants to define a randomness notion with respect to some non-computable measure λ, a choice needs to be made. One approach is to allow randomness tests to access the measure λ as an oracle. The other approach is the opposite one, where the randomness tests are completely effective and do not have access to the information contained in λ. While the Hippocratic approach is in general much more restrictive, there are cases where the two coincide. (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  17.  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  
  18.  10
    A Conflict Between Some Semantic Conditions of Carmo and Jones for Contrary-to-Duty Obligations.Bjørn Kjos-Hanssen - 2017 - Studia Logica 105 (1):173-178.
    We show that Carmo and Jones’ condition 5 conflicts with the other conditions on their models for contrary-to-duty obligations. We then propose a resolution to the conflict.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark