Source author record

Kojiro Higuchi

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Logic in Computer Science math.LO

Catalog footprint

Research overview

4works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

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

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 computable functions on Baire space from the viewpoint of learning theory and piecewise computability. For instance, we show that mind-change-bounded-learnability is equivalent to finite $(Π^0_1)_2$ -piecewise computability (where $(Π^0_1)_2$ denotes the difference of two $Π^0_1$ sets), error-bounded-learnability is equivalent to finite $Δ^0_2$ -piecewise computability, and learnability is equivalent to countable $Π^0_1$ -piecewise computability (equivalently, countable $Σ^0_2$ -piecewise computability). Second, we introduce disjunction-like operations such as the coproduct based on BHK-like interpretations, and then, we see that these operations induce Galois connections between the Medvedev degree structure and associated Medvedev/Muchnik-like degree structures. Finally, we interpret these results in the context of the Weihrauch degrees and Wadge-like games.

preprint2013arXiv

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

It is known that infinitely many Medvedev degrees exist inside the Muchnik degree of any nontrivial $Π^0_1$ subset of Cantor space. We shed light on the fine structures inside these Muchnik degrees related to learnability and piecewise computability. As for nonempty $Π^0_1$ subsets of Cantor space, we show the existence of a finite- $Δ^0_2$ -piecewise degree containing infinitely many finite- $(Π^0_1)_2$ -piecewise degrees, and a finite- $(Π^0_2)_2$ -piecewise degree containing infinitely many finite- $Δ^0_2$ -piecewise degrees (where $(Π^0_n)_2$ denotes the difference of two $Π^0_n$ sets), whereas the greatest degrees in these three "finite- $Γ$ -piecewise" degree structures coincide. Moreover, as for nonempty $Π^0_1$ subsets of Cantor space, we also show that every nonzero finite- $(Π^0_1)_2$ -piecewise degree includes infinitely many Medvedev (i.e., one-piecewise) degrees, every nonzero countable- $Δ^0_2$ -piecewise degree includes infinitely many finite-piecewise degrees, every nonzero finite- $(Π^0_2)_2$ -countable- $Δ^0_2$ -piecewise degree includes infinitely many countable- $Δ^0_2$ -piecewise degrees, and every nonzero Muchnik (i.e., countable- $Π^0_2$ -piecewise) degree includes infinitely many finite- $(Π^0_2)_2$ -countable- $Δ^0_2$ -piecewise degrees. Indeed, we show that any nonzero Medvedev degree and nonzero countable- $Δ^0_2$ -piecewise degree of a nonempty $Π^0_1$ subset of Cantor space have the strong anticupping properties. Finally, we obtain an elementary difference between the Medvedev (Muchnik) degree structure and the finite- $Γ$ -piecewise degree structure of all subsets of Baire space by showing that none of the finite- $Γ$ -piecewise structures are Brouwerian, where $Γ$ is any of the Wadge classes mentioned above.

preprint2013arXiv

Propagation of partial randomness

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"of 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 PA-degree implies strong f-randomness, hence f-randomness does not imply f-randomness relative to a PA-degree.

preprint2013arXiv

The degree structure of Weihrauch-reducibility

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 the existence of infinite infima and suprema, as well as embeddings of the Medvedev-degrees into the Weihrauch-degrees.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Kojiro Higuchi

Research overview

Is this your work?

4 publications

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

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

Propagation of partial randomness

The degree structure of Weihrauch-reducibility

See the researcher in context

Building this map preview