2013/09/08 by Kojiro Higuchi, Higuchi, Kojiro, Takayuki Kihara +1
Computer Science · #(2010): 03D30 (Primary) #03D78 #03E15 #26A21 #68Q32 (Secondary) #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #Machine Learning and Algorithms #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1309.1937
openalex publication_date 2013/09/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is known that infinitely many Medvedev degrees exist inside the Muchnik degree of any nontrivial Π01 subset of Cantor space. We shed light on the fine structures inside these Muchnik degrees related to learnability and piecewise computability. As for nonempty Π01 subsets of Cantor space, we show the existence of a finite-Δ02-piecewise degree containing infinitely many finite-(Π01)2-piecewise degrees, and a finite-(Π02)2-piecewise degree containing infinitely many finite-Δ02-piecewise degrees (where (Π0n)2 denotes the difference of two Π0n sets), whereas the greatest degrees in these three "finite-Γ-piecewise" degree structures coincide. Moreover, as for nonempty Π01 subsets of Cantor space, we also show that every nonzero finite-(Π01)2-piecewise degree includes infinitely many Medvedev (i.e., one-piecewise) degrees, every nonzero countable-Δ02-piecewise degree includes infinitely many finite-piecewise degrees, every nonzero finite-(Π02)2-countable-Δ02-piecewise degree includes infinitely many countable-Δ02-piecewise degrees, and every nonzero Muchnik (i.e., countable-Π02-piecewise) degree includes infinitely many finite-(Π02)2-countable-Δ02-piecewise degrees. Indeed, we show that any nonzero Medvedev degree and nonzero countable-Δ02-piecewise degree of a nonempty Π01 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.