BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Kojiro Higuchi

Kojiro Higuchi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Logic in Computer Sciencemath.LO

Catalog footprint

What is connected

4works
2topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

4 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access