Show simple item record

dc.contributor.authorGacs, Peteren_US
dc.date.accessioned2018-06-19T14:17:25Z
dc.date.available2018-06-19T14:17:25Z
dc.date.issued2005-09-05
dc.identifierhttp://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000231660900006&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=6e74115fe3da270499c3d65c9b17d654
dc.identifier.citationP Gacs. 2005. "Uniform test of algorithmic randomness over a general space." Theoretical Computer Science, Volume 341, Issue 1-3, pp. 91 - 137 (47). https://doi.org/10.1016/j.tcs.2005.03.054
dc.identifier.issn0304-3975
dc.identifier.urihttps://hdl.handle.net/2144/29417
dc.description.abstractThe algorithmic theory of randomness is well developed when the underlying space is the set of finite or infinite sequences and the underlying probability distribution is the uniform distribution or a computable distribution. These restrictions seem artificial. Some progress has been made to extend the theory to arbitrary Bernoulli distributions (by Martin-Löf) and to arbitrary distributions (by Levin). We recall the main ideas and problems of Levin's theory, and report further progress in the same framework. The issues are the following: Allow non-compact spaces (like the space of continuous functions, underlying the Brownian motion). The uniform test (deficiency of randomness) (depending both on the outcome x and the measure P) should be defined in a general and natural way. See which of the old results survive: existence of universal tests, conservation of randomness, expression of tests in terms of description complexity, existence of a universal measure, expression of mutual information as “deficiency of independence”. The negative of the new randomness test is shown to be a generalization of complexity in continuous spaces; we show that the addition theorem survives. The paper's main contribution is introducing an appropriate framework for studying these questions and related ones (like statistics for a general family of distributions).en_US
dc.format.extentp. 91 - 137en_US
dc.languageEnglish
dc.publisherElsevier Science BVen_US
dc.relation.ispartofTHEORETICAL COMPUTER SCIENCE
dc.subjectScience & technologyen_US
dc.subjectTechnologyen_US
dc.subjectComputer science, theory & methodsen_US
dc.subjectComputer scienceen_US
dc.subjectAlgorithmic information theoryen_US
dc.subjectAlgorithmic entropyen_US
dc.subjectRandomness testen_US
dc.subjectKolmogorov complexityen_US
dc.subjectDescription complexityen_US
dc.subjectInformation and computing sciencesen_US
dc.subjectMathematical sciencesen_US
dc.subjectComputation theory & mathematicsen_US
dc.titleUniform test of algorithmic randomness over a general spaceen_US
dc.typeArticleen_US
dc.identifier.doi10.1016/j.tcs.2005.03.054
pubs.elements-sourceweb-of-scienceen_US
pubs.notesEmbargo: No embargoen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Arts & Sciencesen_US
pubs.organisational-groupBoston University, College of Arts & Sciences, Department of Computer Scienceen_US
pubs.publication-statusPublisheden_US


This item appears in the following Collection(s)

Show simple item record