6 found
  1.  22
    Propagation of Partial Randomness.Kojiro Higuchi, W. M. Phillip Hudelson, Stephen G. Simpson & Keita Yokoyama - 2014 - Annals of Pure and Applied Logic 165 (2):742-758.
    Let f be a computable function from finite sequences of 0ʼs and 1ʼs to real numbers. We prove that strong f-randomness implies strong f-randomness relative to a PA-degree. We also prove: if X is strongly f-random and Turing reducible to Y where Y is Martin-Löf random relative to Z, then X is strongly f-random relative to Z. In addition, we prove analogous propagation results for other notions of partial randomness, including non-K-triviality and autocomplexity. We prove that f-randomness relative to a (...)
    Direct download (4 more)  
    Export citation  
    Bookmark   4 citations  
  2.  13
    Weak Theories of Concatenation and Minimal Essentially Undecidable Theories: An Encounter of WTC\documentclass[12pt]{Minimal} \usepackage{Amsmath} \usepackage{Wasysym} \usepackage{Amsfonts} \usepackage{Amssymb} \usepackage{Amsbsy} \usepackage{Mathrsfs} \usepackage{Upgreek} \setlength{\oddsidemargin}{-69pt} \begin{Document}$${\mathsf{WTC}}$$\end{Document} and S2S\documentclass[12pt]{Minimal} \usepackage{Amsmath} \usepackage{Wasysym} \usepackage{Amsfonts} \usepackage{Amssymb} \usepackage{Amsbsy} \usepackage{Mathrsfs} \usepackage{Upgreek} \setlength{\oddsidemargin}{-69pt} \begin{Document}$${\mathsf{S2S}}$$\end{Document}.Kojiro Higuchi & Yoshihiro Horihata - 2014 - Archive for Mathematical Logic 53 (7-8):835-853.
    We consider weak theories of concatenation, that is, theories for strings or texts. We prove that the theory of concatenation WTC-ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{WTC}^{-\varepsilon}}$$\end{document}, which is a weak subtheory of Grzegorczyk’s theory TC-ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{TC}^{-\varepsilon}}$$\end{document}, is a minimal essentially undecidable theory, that is, the theory WTC-ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{WTC}^{-\varepsilon}}$$\end{document} is essentially undecidable and if one omits an axiom scheme from WTC-ε\documentclass[12pt]{minimal} \usepackage{amsmath} (...)
    Direct download (2 more)  
    Export citation  
    Bookmark   2 citations  
  3.  10
    Effective Strong Nullness and Effectively Closed Sets.Kojiro Higuchi & Takayuki Kihara - 2012 - In S. Barry Cooper (ed.), How the World Computes. pp. 303--312.
    Direct download  
    Export citation  
    Bookmark   2 citations  
  4.  16
    On the Strength of Marriage Theorems and Uniformity.Makoto Fujiwara, Kojiro Higuchi & Takayuki Kihara - 2014 - Mathematical Logic Quarterly 60 (3):136-153.
  5.  6
    Effectively Closed Mass Problems and Intuitionism.Kojiro Higuchi - 2012 - Annals of Pure and Applied Logic 163 (6):693-697.
  6.  7
    Defining a Randomness Notion Via Another.Kojiro Higuchi & Ningning Peng - 2014 - Mathematical Logic Quarterly 60 (4-5):280-288.
    No categories
    Direct download (2 more)  
    Export citation