Algorithmically Random Functions and Effective Capacities

DOI10.1007/978-3-319-17142-5_4MaRDI QIDQ2948450zbMATH OpenOpenAlexFDO

Authors Douglas Cenzer, Christopher P. Porter

Publication date 30 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic randomnesscapacitycomputability theoryrandom closed setsrandom continuous functions

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Applications of computability and recursion theory (03D80)

Abstract: We continue the investigation of algorithmically random functions and closed sets, and in particular the connection with the notion of capacity. We study notions of random continuous functions given in terms of a family of computable measures called symmetric Bernoulli measures. We isolate one particular class of random functions that we refer to as online random functions $F$, where the value of $y(n)$ for $y=F(x)$ may be computed from the values of $x(0),dots,x(n)$. We show that random online functions are neither onto nor one-to-one. We give a necessary condition on the members of the ranges of online random functions in terms of initial segment complexity and the associated computable capacity. Lastly, we introduce the notion of online emph{partial} Martin-L"of random function on $2^{o}mega$ and give a family of online partial random functions the ranges of which are precisely the random closed sets introduced by Barmpalias, Brodhead, Cenzer, Dashti, and Weber.

Recommendations

• Algorithmic randomness of continuous functions
• Algorithmic randomness and capacity of closed sets
• On the complexity of finite random functions
• Solovay functions and their applications in algorithmic randomness
• scientific article; zbMATH DE number 3942641
• Algorithmic randomness over general spaces
• scientific article; zbMATH DE number 7311154
• Effective randomness for computable probability measures
• scientific article; zbMATH DE number 4156423

Cites work

• Algorithmic randomness and capacity of closed sets
• Algorithmic Randomness of Closed Sets
• Algorithmic randomness of continuous functions
• K-Triviality of Closed Sets and Continuous Functions
• Martin-Löf randomness and Galton-Watson processes
• Random Continuous Functions
• Strong reductions in effective randomness
• The definition of random sequences

Cited in

(6)

• Algorithmic randomness and capacity of closed sets
• scientific article; zbMATH DE number 4138829 (Why is no real title available?)
• Solovay functions and their applications in algorithmic randomness
• scientific article; zbMATH DE number 7311154 (Why is no real title available?)
• Randomness extraction in computability theory
• Extraction rates of random continuous functionals

This page was built for publication: Algorithmically Random Functions and Effective Capacities

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