Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism

DOI10.1016/J.APAL.2014.01.003MaRDI QIDQ2637708zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 14 February 2014

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.0697

zbMATH Keywords

computable analysisidentification in the limitlimit computable mathematicsMedvedev degreeWeihrauch degree

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Computation over the reals, computable analysis (03D78) Descriptive set theory (03E15) Constructive and recursive analysis (03F60) Computational learning theory (68Q32)

Abstract: 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 $(P{i}_1^0{)}_2$-piecewise computability (where $(P{i}_1^0{)}_2$ denotes the difference of two $P{i}_1^0$ sets), error-bounded-learnability is equivalent to finite $Delt{a}_2^0$-piecewise computability, and learnability is equivalent to countable $P{i}_1^0$-piecewise computability (equivalently, countable $Sigm{a}_2^0$-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.

Recommendations

• Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
• Degrees of unsolvability of continuous functions
• Three topological reducibilities for discontinuous functions
• Revising type-2 computation and degrees of discontinuity
• New Computational Paradigms

Cites work

• (Short) Survey of Real Hypercomputation
• A classification of Baire one star functions
• A sequent calculus for limit computable mathematics
• A splitting theorem for the Medvedev and Muchnik lattices
• A survey of Mučnik and Medvedev degrees
• An application of Martin-Löf randomness to effective probability theory
• An extension of the recursively enumerable Turing degrees
• Analytic machines
• Approximately differentiable functions: The r-topology
• Automata, Languages and Programming
• Borel isomorphisms at the first level, II
• Closed choice and a uniform low basis theorem
• Closed choice for finite and for convex sets
• Coding true arithmetic in the Medvedev and Muchnik degrees
• Computability of a function with jumps: Effective uniformity and limiting recursion
• Decomposing Borel functions using the Shore-Slaman join theorem
• Decomposing Borel sets and functions and the structure of Baire class 1 functions
• Density of the Medvedev lattice of ^0_1 classes
• Effective Borel measurability and reducibility of functions
• Effective Choice and Boundedness Principles in Computable Analysis
• Embeddings into the Medvedev and Muchnik lattices of ^0_1 classes
• First level Borel functions and isomorphisms
• Game representations of classes of piecewise definable functions
• Games with 1-backtracking
• Hierarchies of function classes defined by the first-value operator
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 1303200 (Why is no real title available?)
• scientific article; zbMATH DE number 605140 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 1966601 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• scientific article; zbMATH DE number 1783013 (Why is no real title available?)
• scientific article; zbMATH DE number 845926 (Why is no real title available?)
• scientific article; zbMATH DE number 7311152 (Why is no real title available?)
• scientific article; zbMATH DE number 3250567 (Why is no real title available?)
• scientific article; zbMATH DE number 3342830 (Why is no real title available?)
• scientific article; zbMATH DE number 3110190 (Why is no real title available?)
• Immunity and non-cupping for closed sets
• Intermediate logics and factors of the Medvedev lattice
• Introduction to computability logic
• Learning to win process-control games watching game-masters
• Limiting recursion
• Mass Problems and Randomness
• Mass problems associated with effectively closed sets
• Mathematics based on incremental learning -- excluded middle and inductive inference
• Mind change efficient learning
• More on Wadge determinacy
• Multitape games
• Non-branching degrees in the Medvedev lattice of Π₁⁰ classes
• Non-commutative infinitary Peano arithmetic
• On degrees of unsolvability
• On some class of functions intermediate between the class B^*_1 and the family of continuous functions
• On the (semi)lattices induced by continuous reducibilities
• On the role of procrastination in machine learning
• On the Structure of Finite Level and ω-Decomposable Borel Functions
• Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra
• Real hypercomputation and continuity
• Revising type-2 computation and degrees of discontinuity
• Sequential operators in computability logic
• Some fundamental issues concerning degrees of unsolvability
• Some intuitionistic equivalents of classical principles for degree 2 formulas
• Some remarks on the algebraic structure of the Medvedev Lattice
• Structural measures for games and process control in the branch learning model
• Subsystems of second order arithmetic
• Subsystems of second-order arithmetic between \(\text{RCA}_{0}\) and \(\text{WKL}_{0}\)
• The \(\forall \exists \)-theory of the effectively closed Medvedev degrees is decidable
• The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
• The degree structure of Weihrauch-reducibility
• The Effective Sequence of Uniformities and its Limit as a Methodology in Computable Analysis
• The space of class \alpha Baire functions
• Toggling operators in computability logic
• Topological complexity with continuous operations
• Topological properties of concept spaces (full version)
• Toward a mathematical theory of inductive inference
• Trial and error predicates and the solution to a problem of Mostowski
• Turing degrees and the Ershov hierarchy
• Wadge hierarchy and Veblen hierarchy. I: Borel sets of finite rank
• Weihrauch degrees, omniscience principles and weak computability

Cited in

(11)

• Strong Medvedev reducibilities and the KL-randomness problem
• Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
• Borel-piecewise continuous reducibility for uniformization problems
• Weihrauch degrees of finding equilibria in sequential games
• Fluctuations, effective learnability and metastability in analysis
• On the algebraic structure of Weihrauch degrees
• Revising type-2 computation and degrees of discontinuity
• Levels of discontinuity, limit-computability, and jump operators
• Decomposing Borel functions using the Shore-Slaman join theorem
• Computability of Subsets of Metric Spaces
• Stashing and parallelization pentagons

This page was built for publication: Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2637708)