Genericity and randomness with ITTMs

DOI10.1017/JSL.2019.62MaRDI QIDQ5207572zbMATH OpenOpenAlexWikidataFDO

Authors Benoit Monin, Paul-Elliot Anglès d'Auriac

Publication date 10 January 2020

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/jsl.2019.62

zbMATH Keywords

algorithmic randomnessconstructiblesforcinghigher computabilityITTM

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Recommendations

• RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY
• Algorithmic randomness for infinite time register machines
• Randomness and degree theory for infinite time register machines
• Higher randomness and genericity
• Genericity and randomness over feasible probability measures

Cites work

• Admissible Sets and Structures
• Algorithmic randomness and complexity.
• Computability and randomness
• Continuous higher randomness
• Higher randomness and forcing with closed sets
• Higher randomness and genericity
• scientific article; zbMATH DE number 7204368 (Why is no real title available?)
• scientific article; zbMATH DE number 3289430 (Why is no real title available?)
• Infinite computations with random oracles
• Infinite time Turing machines
• Infinite time Turing machines with only one tape
• Lowness of higher randomness notions
• Notions of weak genericity
• Randomness in the higher setting
• Randomness via effective descriptive set theory
• RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY
• The definition of random sequences
• The Length of Infinite Time Turing Machine Computations

Cited in

(9)

• Genericity, Randomness, and Polynomial-Time Approximations
• On the Weihrauch degree of the additive Ramsey theorem
• Hilbert's tenth problem for term algebras with a substitution operator
• Complemented subsets and Boolean-valued, partial functions
• Defining long words succinctly in FO and MSO
• On the first-order parts of problems in the Weihrauch degrees
• Algorithmically random series
• Ideal presentations and numberings of some classes of effective quasi-Polish spaces
• Lower bounds on () and other properties of -register machines

This page was built for publication: Genericity and randomness with ITTMs

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