On the Defect of Randomness of a Finite Object with Respect to Measures with Given Complexity Bounds
Vladimir Vyacheslavovich V'yugin · Theory of Probability and Its Applications · 1988
Previous article Next article On the Defect of Randomness of a Finite Object with Respect to Measures with Given Complexity BoundsV. V. V'YuginV. V. V'Yuginhttps://doi.org/10.1137/1132071PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout[1] Joseph R. Shoenfield, Degrees of unsolvability, North-Holland Publishing Co., Amsterdam, 1971vii+111 49:4768 0245.02037 Google Scholar[2] A. N. Kolmogorov, On logical foundations of probability theoryProbability theory and mathematical statistics (Tbilisi, 1982), Lecture Notes in Math., Vol. 1021, Springer, Berlin, 1983, 1–5 85h:60007 0519.60002 CrossrefGoogle Scholar[3] A. K. Zvonkin and , L. A. Levin, The complexity of finite objects and the basing of the concepts of information and randomness on the theory of algorithms, Uspehi Mat. Nauk, 25 (1970), 85–127 46:7004 0222.02027 Google Scholar[4] V. V. V'yugin, Algorithmic entropy (complexity) of finite objects and its application to the definition of randomness and amount of informationSemiotika and Informatika, VINITI, Moscow, 1981, 14–43, (In Russian.) 0564.94006 Google Scholar[5] V. V. V'yugin, Nonstochastic objects, Problemy Peredachi Informatsii, 21 (1985), 3–9, (In Russian.) 87d:94026 0578.94009 Google Scholar Previous article Next article FiguresRelatedReferencesCited ByDetails An extended coding theorem with application to quantum complexitiesInformation and Computation | 1 Nov 2020 Cross Ref Sophistication vs Logical DepthTheory of Computing Systems, Vol. 60, No. 2 | 19 March 2016 Cross Ref Algorithmic Statistics: Forty Years LaterComputability and Complexity | 1 December 2016 Cross Ref Rate Distortion and Denoising of Individual Data Using Kolmogorov ComplexityIEEE Transactions on Information Theory, Vol. 56, No. 7 | 1 Jul 2010 Cross Ref Meaningful InformationIEEE Transactions on Information Theory, Vol. 52, No. 10 | 1 Oct 2006 Cross Ref Kolmogorov's Structure Functions and Model SelectionIEEE Transactions on Information Theory, Vol. 50, No. 12 | 1 Dec 2004 Cross Ref Does snooping help?Theoretical Computer Science, Vol. 276, No. 1-2 | 1 Apr 2002 Cross Ref Meaningful InformationAlgorithms and Computation | 8 November 2002 Cross Ref Most Sequences Are StochasticInformation and Computation, Vol. 169, No. 2 | 1 Sep 2001 Cross Ref Algorithmic statisticsIEEE Transactions on Information Theory, Vol. 47, No. 6 | 1 Sep 2001 Cross Ref Kolmogorov's Complexity Conception of ProbabilityProbability Theory | 1 Jan 2001 Cross Ref Minimum description length induction, Bayesianism, and Kolmogorov complexityIEEE Transactions on Information Theory, Vol. 46, No. 2 | 1 Mar 2000 Cross Ref Towards an Algorithmic StatisticsAlgorithmic Learning Theory | 19 October 2001 Cross Ref Algorithmic ComplexityAn Introduction to Kolmogorov Complexity and Its Applications | 1 Jan 1997 Cross Ref Minimum complexity density estimationIEEE Transactions on Information Theory, Vol. 37, No. 4 | 1 Jul 1991 Cross Ref Algorithms and RandomnessA. N. Kolmogorov and V. A. UspenskiiTheory of Probability & Its Applications, Vol. 32, No. 3 | 17 July 2006AbstractPDF (3481 KB) Volume 32, Issue 3| 1988Theory of Probability & Its Applications389-571 History Submitted:17 April 1987Published online:17 July 2006 InformationCopyright © Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/1132071Article page range:pp. 508-512ISSN (print):0040-585XISSN (online):1095-7219Publisher:Society for Industrial and Applied Mathematics