Weihrauch-completeness for layerwise computability

DOI10.23638/LMCS-14(2:11)2018MaRDI QIDQ4643953zbMATH OpenFDO

Authors Arno Pauly, George Davie, Willem Louw Fouché

Publication date 30 May 2018

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

zbMATH Keywords

computable analysislayerwise computabilityrandomnessWeihrauch reducibility

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Computation over the reals, computable analysis (03D78) Constructive and recursive analysis (03F60)

Recommendations

• Weihrauch degrees, omniscience principles and weak computability
• Weihrauch degrees, omniscience principles and weak computability
• The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
• Completion of choice
• L^1-computability, layerwise computability and Solovay reducibility

Cites work

• A computable version of the random signs problem and Kolmogorov complexity
• A constructive Borel-Cantelli lemma. Constructing orbits with required statistical properties
• A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points
• A topological view on algebraic computation models
• Admissible representations for probability measures
• Algorithmically random series and Brownian motion
• An application of Martin-Löf randomness to effective probability theory
• Applications of Effective Probability Theory to Martin-Löf Randomness
• Closed choice and a uniform low basis theorem
• Computability and randomness
• Computability of probability measures and Martin-Löf randomness over metric spaces
• Descriptive set theory in the category of represented spaces
• Dynamics of a generic Brownian motion: Recursive aspects
• Effective Choice and Boundedness Principles in Computable Analysis
• How incomputable is finding Nash equilibria?
• Martin-Löf random points satisfy Birkhoff's ergodic theorem for effectively closed sets
• On the (semi)lattices induced by continuous reducibilities
• On the algebraic structure of Weihrauch degrees
• On the computability of a construction of Brownian motion
• Random harmonic series
• The Borel-Cantelli lemmas, probability laws and Kolmogorov complexity
• The definition of random sequences
• The degree structure of Weihrauch-reducibility
• The descriptive complexity of Brownian motion
• The difference between optimality and universality
• The Law of the Iterated Logarithm for Random Kolmogorov, or Chaotic, Sequences
• The Vitali Covering Theorem in the Weihrauch Lattice
• Universality, optimality, and randomness deficiency
• Use of the Kolmogorov complexity in analyzing control system dynamics
• Weihrauch degrees, omniscience principles and weak computability
• Эффективная сходимость по вероятности и эргодическая теорема для индивидуальных случайных последовательностей

Cited in

(9)

• Comparing representations for function spaces in computable analysis
• A topological view on algebraic computation models
• Pointwise complexity of the derivative of a computable function
• Universality, optimality, and randomness deficiency
• L^1-computability, layerwise computability and Solovay reducibility
• Weihrauch Complexity in Computable Analysis
• Computability of convergence rates in the ergodic theorem for Martin-Löf random points
• Reduction games, provability and compactness
• Representations of analytic functions and Weihrauch degrees

This page was built for publication: Weihrauch-completeness for layerwise computability

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