Probabilistic computability and choice

DOI10.1016/j.ic.2015.03.005zbMath1320.03071arXiv1312.7305OpenAlexW2023962937MaRDI 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

zbMATH Keywords

computability theoryreverse mathematicsrandomized algorithmscomputable analysisweak weak König's lemmaprobabilistic Turing machineWeihrauch latticeLas Vegas computable functionsrandomized computations on infinite objects

Mathematics Subject Classification ID

Related Items (29)

On the uniform computational content of the Baire category theorem ⋮ Comparing representations for function spaces in computable analysis ⋮ Computability and Analysis, a Historical Approach ⋮ Weihrauch Degrees of Finding Equilibria in Sequential Games ⋮ Parameterized games of perfect information ⋮ A topological view on algebraic computation models ⋮ Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract) ⋮ Algebraic properties of the first-order part of a problem ⋮ On computability and disintegration ⋮ On the uniform computational content of computability theory ⋮ ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM ⋮ 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 ⋮ Completion of choice ⋮ Unnamed Item ⋮ Game characterizations and lower cones in the Weihrauch degrees ⋮ FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS ⋮ On the algebraic structure of Weihrauch degrees ⋮ Representations of Analytic Functions and Weihrauch Degrees ⋮ Game characterizations and lower cones in the Weihrauch degrees ⋮ Automatic learning from positive data and negative counterexamples ⋮ Unnamed Item ⋮ SEARCHING FOR AN ANALOGUE OF ATR₀ IN THE WEIHRAUCH LATTICE ⋮ Computable Measure Theory and Algorithmic Randomness ⋮ Weihrauch Complexity in Computable Analysis ⋮ Lawvere-Tierney topologies for computability theorists

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

This page was built for publication: Probabilistic computability and choice