Výsledky vyhledávání - "Higuchi, Kojiro"

Report

A Note on a Conjecture of Sacks: It is Harder to Embed Height Three Partial Orders than Height Two Partial Orders

A long-standing conjecture of Sacks states that it is provable in ZFC that every locally countable partial order of size continuum embeds into the Turing degrees. We show that this holds for partial orders of height two, but provide evidence that it

Externí odkaz: http://arxiv.org/abs/2309.01876

Zobrazit plný text záznamu

Report

On the order dimension of locally countable partial orderings

Autor: Higuchi, Kojiro, Lempp, Steffen, Raghavan, Diip, Stephan, Frank

We show that the order dimension of the partial order of all finite subsets of $\kappa$ under set inclusion is ${\log}_{2}({\log}_{2}(\kappa))$ whenever $\kappa$ is an infinite cardinal. We also show that the order dimension of any locally countable

Externí odkaz: http://arxiv.org/abs/1902.06030

Zobrazit plný text záznamu

Report

Propagation of partial randomness

Autor: Higuchi, Kojiro, Hudelson, W. M. Phillip, Simpson, Stephen G., Yokoyama, Keita

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

Externí odkaz: http://arxiv.org/abs/1311.0724

Zobrazit plný text záznamu

Report

Inside the Muchnik Degrees II: The Degree Structures induced by the Arithmetical Hierarchy of Countably Continuous Functions

Autor: Higuchi, Kojiro, Kihara, Takayuki

It is known that infinitely many Medvedev degrees exist inside the Muchnik degree of any nontrivial $\Pi^0_1$ subset of Cantor space. We shed light on the fine structures inside these Muchnik degrees related to learnability and piecewise computabilit

Externí odkaz: http://arxiv.org/abs/1309.1937

Zobrazit plný text záznamu

Report

Inside the Muchnik Degrees I: Discontinuity, Learnability, and Constructivism

Autor: Higuchi, Kojiro, Kihara, Takayuki

Every computable function has to be continuous. To develop computability theory of discontinuous functions, we study low levels of the arithmetical hierarchy of nonuniformly computable functions on Baire space. First, we classify nonuniformly computa

Externí odkaz: http://arxiv.org/abs/1210.0697

Zobrazit plný text záznamu

Report

The degree structure of Weihrauch-reducibility

Autor: Higuchi, Kojiro, Pauly, Arno

Publikováno v: Logical Methods in Computer Science, Volume 9, Issue 2 (April 2, 2013) lmcs:1124

We answer a question by Vasco Brattka and Guido Gherardi by proving that the Weihrauch-lattice is not a Brouwer algebra. The computable Weihrauch-lattice is also not a Heyting algebra, but the continuous Weihrauch-lattice is. We further investigate t

Externí odkaz: http://arxiv.org/abs/1101.0112

Zobrazit plný text záznamu