Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism
From MaRDI portal
Publication:2637708
DOI10.1016/j.apal.2014.01.003zbMath1315.03071arXiv1210.0697MaRDI QIDQ2637708
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
computable analysis; identification in the limit; limit computable mathematics; Medvedev degree; Weihrauch degree
68Q32: Computational learning theory
03E15: Descriptive set theory
03F60: Constructive and recursive analysis
03D30: Other degrees and reducibilities in computability and recursion theory
03D78: Computation over the reals, computable analysis
Related Items
On the algebraic structure of Weihrauch degrees, Unnamed Item, Decomposing Borel functions using the Shore–Slaman join theorem, Computability of Subsets of Metric Spaces, Fluctuations, effective learnability and metastability in analysis, 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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
- Closed choice and a uniform low basis theorem
- Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra
- Toggling operators in computability logic
- Games with 1-backtracking
- Embeddings into the Medvedev and Muchnik lattices of \(\Pi^0_1\) classes
- Mass problems associated with effectively closed sets
- Mathematics based on incremental learning -- excluded middle and inductive inference
- More on Wadge determinacy
- Subsystems of second-order arithmetic between \(\text{RCA}_{0}\) and \(\text{WKL}_{0}\)
- Intermediate logics and factors of the Medvedev lattice
- Topological properties of concept spaces (full version)
- Immunity and non-cupping for closed sets
- Sequential operators in computability logic
- First level Borel functions and isomorphisms
- Approximately differentiable functions: The r-topology
- Analytic machines
- On the role of procrastination in machine learning
- Density of the Medvedev lattice of \(\Pi^0_1\) classes
- Introduction to computability logic
- Structural measures for games and process control in the branch learning model
- Computability of a function with jumps: Effective uniformity and limiting recursion
- Learning to win process-control games watching game-masters
- Topological complexity with continuous operations
- Some intuitionistic equivalents of classical principles for degree 2 formulas
- A classification of Baire one star functions
- A sequent calculus for limit computable mathematics
- Mind change efficient learning
- On degrees of unsolvability
- Real hypercomputation and continuity
- The \(\forall \exists \)-theory of the effectively closed Medvedev degrees is decidable
- Wadge hierarchy and Veblen hierarchy Part I: Borel sets of finite rank
- A Survey of Mučnik and Medvedev Degrees
- Non-Commutative Infinitary Peano Arithmetic
- On the (semi)lattices induced by continuous reducibilities
- Game representations of classes of piecewise definable functions
- Weihrauch degrees, omniscience principles and weak computability
- Coding true arithmetic in the Medvedev and Muchnik degrees
- Effective Choice and Boundedness Principles in Computable Analysis
- Effective Borel measurability and reducibility of functions
- Mass Problems and Randomness
- Non-branching degrees in the Medvedev lattice of Π10 classes
- Some remarks on the algebraic structure of the Medvedev Lattice
- Hierarchies of function classes defined by the first-value operator
- The Effective Sequence of Uniformities and its Limit as a Methodology in Computable Analysis
- An Application of Martin-Löf Randomness to Effective Probability Theory
- Borel isomorphisms at the first level, II
- The space of class $\alpha$ Baire functions
- Toward a mathematical theory of inductive inference
- Decomposing Borel sets and functions and the structure of Baire class 1 functions
- A splitting theorem for the Medvedev and Muchnik lattices
- Revising Type-2 Computation and Degrees of Discontinuity
- The degree structure of Weihrauch-reducibility
- Decomposing Borel functions using the Shore–Slaman join theorem
- An extension of the recursively enumerable Turing degrees
- Closed Choice for Finite and for Convex Sets
- On the Structure of Finite Level and ω-Decomposable Borel Functions
- (Short) Survey of Real Hypercomputation
- Automata, Languages and Programming
- Trial and error predicates and the solution to a problem of Mostowski
- Limiting recursion
