Coding-theorem like behaviour and emergence of the universal distribution from resource-bounded algorithmic probability

References

• Levin LA . Laws of information conservation (non-growth) and aspects of the foundation of probability theory. Prob Inf Transm. 1974;10(3):206–210.
   Google Scholar
• Solomonoff RJ . A formal theory of inductive inference: parts 1 and 2. Inf Control. 1964;7:1–22 and 224--254.
   Google Scholar
• Kraft LG . A device for quantizing, grouping, and coding amplitude modulated pulses [MS Thesis]. Cambridge (MA): Electrical Engineering Department, Massachusetts Institute of Technology; 1949.
   Google Scholar
• Solomonoff RJ . Complexity-based induction systems: comparisons and convergence theorems. IEEE Trans Inf Theory. 1978;24(4):422–432.
   Google Scholar
• Solomonoff RJ . The application of algorithmic probability to problems in artificial intelligence. In: Kanal LN , Lemmer JF , editors. Uncertainty in artificial intelligence. Elsevier; 1986. p. 473–491.
   Google Scholar
• Solomonoff RJ . A System for incremental learning based on algorithmic probability. In: Proceedings of the Sixth Israeli Conference on Artificial Intelligence, Computer Vision and Pattern Recognition; 1989 Dec. p. 515–527.
   Google Scholar
• Kirchherr W , Li M , Vitányi P . The Miraculous Universal Distribution. Math Intelligencer. 1997;19:7–15.
   Google Scholar
• Gauvrit N , Zenil H , Soler-Toscano F , et al . Human behavioral complexity peaks at age 25. PLoS Comput Biol. 2017;13(4):e1005408.
   Google Scholar
• Kempe V , Gauvrit N , Forsyth D . Structure emerges faster during cultural transmission in children than in adults. Cognition. 2014;136:247–254.
   Google Scholar
• Gauvrit N , Soler-Toscano F , Zenil H . Natural scene statistics mediate the perception of image complexity. Visual Cognition. 2014;22(8):1084–1091.
   Google Scholar
• Zenil H , Soler-Toscano F , Dingle K , et al . Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks. Physica A. 2014;404:341–358.
   Google Scholar
• Zenil H , Kiani NA , Tegnér J . Methods of information theory and algorithmic complexity for network biology. Sem Cell Dev Biol. 2016;51:32–43.
   Google Scholar
• Schmidhuber J . Optimal ordered problem solver. Mach Learn. 2004;54:211–254.
   Google Scholar
• Schmidhuber J , Zhumatiy V , Gagliolo M . Bias-optimal incremental learning of control sequences for virtual robots. In: Groen F , Amato N , Bonarini A , et al. , editors. Proceedings of the 8th conference on Intelligent Autonomous Systems, IAS-8. Amsterdam, The Netherlands; 2004. p. 658–665.
   Google Scholar
• Steunebrink BR , Schmidhuber J . Towards an actual Gödel machine implementation. In: Wang P , Goertzel B , editors. Theoretical foundations of artificial general intelligence. Springer; 2012.
   Google Scholar
• Hutter M . A theory of universal artificial intelligence based on algorithmic complexity. Springer; 2000.
   Google Scholar
• Antunes L , Fortnow L . Time-bounded universal distributions, electronic colloquium on computational complexity. Report No. 144. 2005.
   Google Scholar
• Wiering M , Schmidhuber J . Solving, POMDPs using Levin search and EIRA. In: Proceedings of the International Conference on Machine Learning (ICML); 1996. p. 534–542.
   Google Scholar
• Levin LA . Universal sequential search problems. Prob Inf Transm. 1973;9:265–266.
   Google Scholar
• Dingle K , Schaper S , Louis AA . The structure of the genotype-phenotype map strongly constrains the evolution of non-coding RNA. Interface Focus. 2015;5:20150053.
   Google Scholar
• Greenbury SF , Johnston IG , Louis AA , et al . A tractable genotype-phenotype map for the self-assembly of protein quaternary structure. Soc Interface. 2014;11:20140249.
   Google Scholar
• Schaper S , Louis AA . The arrival of the frequent: how bias in genotype-phenotype maps can steer populations to local optima. PLoS ONE. 2014;9(2):e86635.
   Google Scholar
• Hernández-Orozco S , Zenil H , Kiani NA . Algorithmically probable mutations reproduce aspects of evolution such as convergence rate, genetic memory, modularity, diversity explosions, and mass extinction. 2017. arXiv:1709.00268 [cs.NE].
   Google Scholar
• Calude CS , Salomaa K , Roblot TK . Finite-state complexity. Theor Comput Sci. 2011;412(41):5668–5677.
   Google Scholar
• Wharton RM . Grammar enumeration and inference. Inf Control. 1977;33(3):253–272.
   Google Scholar
• Delahaye J-P , Zenil H . Numerical evaluation of the complexity of short strings: a glance into the innermost structure of algorithmic randomness. Appl Math Comput. 2012;219:63–77.
   Google Scholar
• Soler-Toscano F , Zenil H , Delahaye J.P. , et al . Calculating Kolmogorov complexity from the output frequency distributions of small Turing machines. PloS one. 2014;9(5):e96223.
   Google Scholar
• Chaitin GJ . On the length of programs for computing finite binary sequences. J ACM. 1966;13(4):547–569.
   Google Scholar
• Campeanu C , Culik K II , Salomaa K , et al . State complexity of basic operations on finite languages. In: Boldt O , Jürgensen H , editors. WIA 1999, LNCS. vol. 2214. Heidelberg: Springer; 2001. p. 60–70.
   Google Scholar
• Hopcroft JE , Ullman JD . Formal languages and their relation to automata. Addison-Wesley Educational Publishers; 1969.
   Google Scholar
• Rangel-Mondragon J . Recognition and parsing of context-free. 2017. [cited Aug 15]. Available from: http://library.wolfram.com/infocenter/MathSource/3128/
   Google Scholar
• Bienvenu L , Downey R . Kolmogorov complexity and Solovay functions. In: STACS, volume 3 of LIPIcs. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik; 2009. p. 147–158.
   Google Scholar
• Hölzl R , Kräling T , Merkle W . Time-bounded Kolmogorov complexity and Solovay functions. Theory Comput Syst. 2013;52(1):80–94.
   Google Scholar
• Rado T . On non-computable functions. Bell Syst Tech J. 1962;41(3):877–884.
   Google Scholar
• Wolfram S . A new kind of science. Champaign (IL): Wolfram Media; 2002.
   Google Scholar
• Peled BY , Mishra VK , Carmi AY . Computing by nowhere increasing complexity. 2017. arXiv:1710.01654 [cs.IT].
   Google Scholar
• Zenil H , Delahaye J-P . On the Algorithmic Nature of the World. In: Dodig-Crnkovic G , Burgin M , editors. Information and computation. World Scientific Publishing Company; 2010.
   Google Scholar
• Delahaye J-P , Zenil H . Towards a stable definition of Kolmogorov-Chaitin complexity. 2008. arXiv:0804.3459 [cs.IT].
   Google Scholar
• Zenil H , Soler-Toscano F , Delahaye J-P , et al . Two-dimensional Kolmogorov complexity and validation of the coding theorem method by compressibility. PeerJ Comput Sci. 2015;1:e23.
   Google Scholar
• Soler-Toscano F , Zenil H , Delahaye J-P , et al . Correspondence and Independence of Numerical Evaluations of Algorithmic Information Measures. Computability. 2013;2(2):125–140.
   Google Scholar
• Soler-Toscano F , Zenil H . A computable measure of algorithmic probability by finite approximations with an application to integer sequences. Complexity. accepted.
   Google Scholar