Probabilistic computability and choice
From MaRDI portal
Publication:2346414
DOI10.1016/j.ic.2015.03.005zbMath1320.03071arXiv1312.7305MaRDI QIDQ2346414
Guido Gherardi, Vasco Brattka, Rupert Hölzl
Publication date: 1 June 2015
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1312.7305
computability theory; reverse mathematics; randomized algorithms; computable analysis; weak weak König's lemma; probabilistic Turing machine; Weihrauch lattice; Las Vegas computable functions; randomized computations on infinite objects
68W20: Randomized algorithms
03F35: Second- and higher-order arithmetic and fragments
03D10: Turing machines and related notions
03D78: Computation over the reals, computable analysis
Related Items
On computability and disintegration, ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM, On the algebraic structure of Weihrauch degrees, Unnamed Item, Unnamed Item, Computable Measure Theory and Algorithmic Randomness, Weihrauch Complexity in Computable Analysis, Game characterizations and lower cones in the Weihrauch degrees, FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS, Representations of Analytic Functions and Weihrauch Degrees, SEARCHING FOR AN ANALOGUE OF ATR0 IN THE WEIHRAUCH LATTICE, Lawvere-Tierney topologies for computability theorists, Algebraic properties of the first-order part of a problem, On the uniform computational content of the Baire category theorem, Comparing representations for function spaces in computable analysis, A topological view on algebraic computation models, On the uniform computational content of computability theory, Game characterizations and lower cones in the Weihrauch degrees, Automatic learning from positive data and negative counterexamples, Parameterized games of perfect information, Completion of choice, Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract), The Vitali Covering Theorem in the Weihrauch Lattice, Parallel and Serial Jumps of Weak Weak König’s Lemma, Many-one reductions and the category of multivalued functions, Borel-Piecewise Continuous Reducibility for Uniformization Problems, STRONG REDUCTIONS BETWEEN COMBINATORIAL PRINCIPLES, Computability and Analysis, a Historical Approach, 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
- The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
- Closed choice and a uniform low basis theorem
- Computable de Finetti measures
- How incomputable is the separable Hahn-Banach theorem?
- Computable invariance
- Random elements in effective topological spaces with measure.
- Computability on subsets of metric spaces.
- Mind change complexity of inferring unbounded unions of restricted pattern languages from positive data
- Topological complexity with continuous operations
- Computability of probability measures and Martin-Löf randomness over metric spaces
- Uniform test of algorithmic randomness over a general space
- Real hypercomputation and continuity
- Non-cooperative games
- On uniform relationships between combinatorial problems
- Representations of measurable sets in computable measure theory
- Long cycles in vertex-transitive graphs
- On the (semi)lattices induced by continuous reducibilities
- Weihrauch degrees, omniscience principles and weak computability
- Effective Choice and Boundedness Principles in Computable Analysis
- Effective Borel measurability and reducibility of functions
- Algorithmic Randomness and Complexity
- Computational complexity on computable metric spaces
- Notions of Probabilistic Computability on Represented Spaces
- Revising Type-2 Computation and Degrees of Discontinuity
- The degree structure of Weihrauch-reducibility
- Degrees of unsolvability of continuous functions
- Closed Choice for Finite and for Convex Sets
- Algorithmic Game Theory
- Degrees of Unsolvability. (AM-55)
- ∏ 0 1 Classes and Degrees of Theories
- Measure and integration theory. Transl. from the German by Robert B. Burckel
