dc.contributor.author Gacs, Peter en_US dc.date.accessioned 2018-06-19T14:17:25Z dc.date.available 2018-06-19T14:17:25Z dc.date.issued 2005-09-05 dc.identifier http://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.citation P 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.issn 0304-3975 dc.identifier.uri https://hdl.handle.net/2144/29417 dc.description.abstract The 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: en_US 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). dc.format.extent p. 91 - 137 en_US dc.language English dc.publisher Elsevier Science BV en_US dc.relation.ispartof THEORETICAL COMPUTER SCIENCE dc.subject Science & technology en_US dc.subject Technology en_US dc.subject Computer science, theory & methods en_US dc.subject Computer science en_US dc.subject Algorithmic information theory en_US dc.subject Algorithmic entropy en_US dc.subject Randomness test en_US dc.subject Kolmogorov complexity en_US dc.subject Description complexity en_US dc.subject Information and computing sciences en_US dc.subject Mathematical sciences en_US dc.subject Computation theory & mathematics en_US dc.title Uniform test of algorithmic randomness over a general space en_US dc.type Article en_US dc.identifier.doi 10.1016/j.tcs.2005.03.054 pubs.elements-source web-of-science en_US pubs.notes Embargo: No embargo en_US pubs.organisational-group Boston University en_US pubs.organisational-group Boston University, College of Arts & Sciences en_US pubs.organisational-group Boston University, College of Arts & Sciences, Department of Computer Science en_US pubs.publication-status Published en_US
﻿