4.6 Convergence of Definitions

Unit 4 Module 6
Algorithmic Information Dynamics: A Computational Approach to Causality and Living Systems---From Networks to Cells
by Hector Zenil and Narsis A. Kiani

Algorithmic Dynamics Lab

Refs:

- G.J. Chaitin. Algorithmic Information Theory, Cambridge University Press, Cambridge, 1987.

- A.N. Kolmogorov, Three approaches to the quantitative definition of information, Problems of Information Transmission 1, 1-11, 1965.

- F. Soler-Toscano, H. Zenil, J.-P. Delahaye, N. Gauvrit, Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines, arXiv:1211.1302 [cs.IT]

- R. J. Solomonoff, A formal theory of inductive inference: Parts 1 and 2. Information and Control, 7:1--22 and 224--254, 1964.

- A. K. Zvonkin and L. A. Levin, The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms, Russian Mathematical Surveys, 25(6):83--124, 1970.

- P.Martin-Löf, The definition of random sequences, Information and Control. 9 (6): 602\[Dash]619, 1966.

- L.A. Levin, On the notion of a random sequence, Soviet Mathematics - Doklady. 14: 1413\[Dash]1416, 1973.

- L.A. Levin, Laws of information conservation (non-growth) and aspects of the foundation of probability theory, Problems Information Transmission, 10(3):206-210, 1974.

- R. J. Solomonoff, "Algorithmic Probability\[LongDash]Its Discovery\[LongDash]Its Properties and Application to Strong AI," In H. Zenil (ed), Randomness Through Computation: Some Answers, More Questions, World Scientific, 2012.

- C.P. Schnorr, Zufalligkeit und Wahrscheinlichkeit, in: Lecture Notes in Math., vol. 218, Springer-Verlag, Berlin, 1971.

- R.G. Downey and D.R. Hirschfeldt, Algorithmic Randomness and Complexity, Springer-Verlag New York, 2010.

- A. Nies, André, Computability and randomness. Oxford Logic Guides. 51. Oxford, Oxford University Press.

- C.P. Schnorr, A unified approach to the definition of a random sequence, Mathematical Systems Theory, 5 (3) : 246\[Dash]258, 1971.

- C.P. Schnorr, Process complexity and effective random tests, Journal of Computer and System Sciences.7 (4) : 376\[Dash]388, 1973.

- H. Zenil, Compression-based Investigation of the Dynamical Properties of Cellular Automata and Other Systems, Complex Systems, vol. 19, No. 1, pp. 1-28, 2010.

- H. Zenil, Asymptotic Behaviour and Ratios of Complexity in Cellular Automata Rule Spaces, International Journal of Bifurcation and Chaos vol. 23, no. 9, 2013.

- H. Zenil, "Cellular Automaton Compressibility", Wolfram Demonstrations Project, Published: March 7 2011

[afterthesmash]

John von Neumann cautioned about the misinterpretation of a PRNG as a truly random generator, and joked that "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."

Yet we use strong PRNGs all the time, and it rarely causes problems, because the vast majority of computer programs are decorrelated from the algorithm that generates the PRNG values. Unfortunately, when it happens that your producer of PRNs and your consumer of PRNs _are_ correlated (there's not automatic detection for this), there's potentially hell to pay.