Le concept de suite aléatoire et la thèse de Church

Delahaye, Jean-Paul

Séminaire de Philosophie et Mathématiques, Le concept de suite aléatoire et la thèse de Church, no. 3 (1991), pp. 1-35.

[Barzdin' 1968] Y. M. Barzdin'. The Complexity of Programs to Determine Whether Natural Numbers not Greater thann, Belong to a Recursively Enumerable Set. Soviet Math. Dokl. 9. 1968. pp. 1251-1254. | Zbl

[Bennett 1979] C. H. Bennett. On Random and Hard-to-Describe Numbers. IBM Research Report RC 7483 1-16-79, IBM Watson Research Center. 1979.

[Bennett 1988] C. H. Bennett. Logical Depth and Physical Complexity. In "The Universal Turing Machine : A Half-Century Survey". Edited by R. Herken. Oxford University Press. 1988. pp. 227-257. | MR | Zbl

[Blum Micali 1984] M. Blum, S. Micali. How to Generate Cryptographically Strong Sequences of Pseudo-Random bits. SIAM J. Comp. 13. 1984. pp. 850-864. | MR | Zbl

[Borel 1909] E. Borel. Presque tous les nombres réels sont normaux. Rend. Circ. Mat. Palermo. 27. 1909. pp. 247-271. | JFM

[Chaitin 1966] G. J. Chaitin. On the Length of Programs for Computing Finite Binary Sequences. J. A.C.M. 13. 1966. pp.547-569. Repris dans [Chaitin 1987a]. | MR | Zbl

[Chaitin 1969a] G. J. Chaitin. On the Length of Programs for Computing Finite Binary Sequences, Statistical Considerations. J.A.C.M. 16. 1969. pp.145-159. Repris dans [Chaitin 1987a]. | MR | Zbl

[Chaitin 1974] G. L. Chaitin. Information Theoretic Limitations of Formal Systems. J.A.C.M. 1974. pp. 403-424. Repris dans [Chatin 87a]. | MR | Zbl

[Chaitin 1975a] G. L. Chaitin. A theory of program size formally identical to information theory. J.A.C.M. 22. 1975. pp. 329-340. Repris dans [Chaitin 87a]. | MR | Zbl

[Chaitin 1975b] G. J. Chaitin. Randomness and Mathematical Proof. Scientific American. 232. May 1975. pp. 47-52.

[Chaitin 1979] G. J. Chaitin. Toward a mathematical definition of "life". In "The Maximum Entropy Formalism". R. D. Levine and M. Tribus Edrs. MIT Press. 1979. pp. 477-498. Repris dans [Chaitin 1987a]. | MR

[Chaitin 1987a] G. J. Chaitin. Information, Randomness and Incompleteness : Papers on Algorithmic Information Theory. World Scientific, Singapore, 1987. | MR | Zbl

[Chaitin 1987b] G. J. Chaitin. Algorithmic information theory. Cambridge Tracts in Theoretical Computer Science 1. Cambridge University Press, New York, 1987. | MR | Zbl

[Chaitin 1987c] G. J. Chaitin. Incompleteness Theorems for Random Reals. Advances in Applied Mathematics. 8. 1987. pp. 119-146. Repris dans [Chaitin 1987a] | MR | Zbl

[Chaitin 1988] G. J. Chaitin. Randomness in Arithmetic. Scientific American. July 1988. pp. 80-85. | Zbl

[Chaitin Schwartz 1978] G. J. Chaitin and J.T. Schwartz. A note on Monte Carlo Primality Tests and Algorithmic Information Theory. Communication on Pure and Applied Mathematics. 31. 1978. pp. 521-527. Repris dans [Chaitin 1987a]. | MR | Zbl

[Champernowne 1933] D. G. Champernowne. The construction of decimal normal in the scale of ten. J. London Math. Soc. 8. 1933. pp. 254-260. | MR | Zbl

[Chor Goldreich 1988] B. Chor, O. Goldreich. Unbiased bits Sources of Weak randomness and Probabilistic Communication Complexity. SIAM J. Comp. 17, 2. 1988. pp. 230-261. | MR | Zbl

[Church 1940] A. Church. On the concept of a random sequence. Bulletin Amer. Math. Soc. 46. 1940. pp. 130-135. | JFM | MR

[Cover Gacs Gray 1989] T. M. Cover, P. Gacs, R. M. Gray. Kolmogorov's contributions to information theory and algorithmic complexity. The Annals of Probability, Vol 17, n°3, 1989, pp. 840-865. | MR | Zbl

[Daley 1973] R. P. Daley. Minimal-Program Complexity of Sequence with Restricted Resources. Information and Control. 23. 1973. pp. 301-312. | MR | Zbl

[Daley 1975] R.P. Daley. Minimal-Program Complexity of Pseudo-Recursive and Pseudo-Random Sequences. Mathematical System Theory, vol 9, n° 1, 1975. pp. 83-94. | MR | Zbl

[Daley 1976] R.P. Daley. Noncomplex Sequences : Characterizations and Examples. J. Symbol. Logic. 41. 1976. pp. 626 | MR | Zbl

[Delahaye 1988a] J.P. Delahaye. Une Extension Spectaculaire du Théorème de Gödel. La Recherche n°200, juin 1988. pp. 860-862.

[Delahaye 1988b] J.P. Delahaye. Sequence transformations. Springer-Verlag, Series in Computational Mathematics. Berlin. 1988. | MR | Zbl

[Delahaye 1989a] J.P. Delahaye. Cinq Classes d'Idées. Rapport Laboratoire d'Informatique Fondamentale de Lille. Univ. Sc. Lille, Bât M3, 59655 Villeneuve d'Ascq. Avril 1989.

[Delahaye 1989b] J.-P. Delahaye. Chaitin's Equation : An Extension of Gödel's Theorem. Notices of The American Mathematical Society. October 1989. pp. 984-987. | Zbl

[Delahaye 1990] J.-P. Delahaye. Randomness, Unpredictability and Absence of Order. Colloque International sur la Philosophie des Probabilités. Organisé par le CNRS et l'Institut d'Histoire des Sciences de Paris, 10-11-12 Mai 1990, Paris. A paraître : Kluwer Academic Publ.

[Dies 1976 1978] J. E. Dies. Information et Complexité. Annales de L'institut Henry Poincaré, Section B, Calcul des Probabilités et Statistiques. Nouvelle Série Vol 12. 1976. pp. 365-390. | Numdam | MR | Zbl

J. E. Dies. Information et Complexité. Annales de L'institut Henry Poincaré, Section B, Calcul des Probabilités et Statistiques. Vol 14. 1978. pp. 113-118. | Numdam | MR | Zbl

[Fine 1973] T. Fine. Theories of Probability. Academic Press. New-York. 1973. | MR | Zbl

[Gacs 1974] P. Gacs. On the symmetry of algorithmic information. Dokl. Akad. Nauk SSSR. 218. 1974. pp. 1477-1480. | MR | Zbl

[Gacs 1980] P. Gacs. Exact Expressions for Some Randomness Tests. Z. Math. Logik. Grundl. Math. 26. 1980. | MR | Zbl

[Gacs 1983] P. Gacs. On the relation between descriptional complexity and probability. Theo. Comp. 22. 1983. pp. 71-93. | MR | Zbl

[Gacs 1986] P. Gacs. Every Sequence Is Reducible to a Random One. Information and Control. 70. 1986. pp. 186-192. | MR | Zbl

[Gaifman Snir 1982] H. Gaifman, M. Snir. Probabilities over rich languages, randomness and testing. Journal of Symbolic Logic. Vol. 47. 1982. pp. 495-548. | MR | Zbl

[Gardner 1980] M. Gardner. Le nombre aléatoire oméga semble bien recéler les mystères de l'univers. Pour La Science. 1980.

[Goldreich 1988] O. Goldreich. Randomness, Interactive Proofs, and Zero-Knowledge. In "The Universal Turing Machine : A Half-Century Survey". Edited by R. Herken. Oxford University Press. 1988. pp. 376-405. | MR | Zbl

[Goldreich Goldwasser Micali 1986] O. Goldreich, S. Goldwasser, S. Micali. How to construct random functions. J. A. C. M. 33, 4. 1986. pp. 792-807. | MR | Zbl

[Ko 1986] K. Ko. On the notion of Infinite pseudo-random sequences. Theoretical Computer Science. 48. 1986. pp. 9-33 | MR | Zbl

[Kolmogorov 1933] A. N. Kolmogorov. Grundbegriffe der Wahrscheinlichkeitsrechnung. Springer Verlag, Berlin, 1933. (2nd Russian Edition 1974, 'Osnovnye Poniatija Teorii Verojatnostej' Nauka, Moscow) | MR | Zbl

[Kolmogorov 1936] A. N. Kolmogorov. Osnovye ponyatiya teorii veroyatnostei. ONTI. Moscow, 1936. Traduction anglaise : Foundations of the theory of probability. Chelsea, New-York. 1950.

[Kolmogorov 1963] A. N. Kolmogorov. On table of random numbers. Sankhya The Indian Journal of Statistics. A25. 369. 1963. pp. 369-376. | MR | Zbl

[Kolmogorov 1965] A. N. Kolmogorov. Three approaches for defining the concept of information quantity. Information Transmission. V. 1. 1965. pp. 3-11. | MR | Zbl

[Kolmogorov 1968] A. N. Kolmogorov. Logical basis for Information Theory and Probability Theory. IEEE Transaction on Information Theory. Vol. IT14, n°5. 1968. pp. 662-664. | MR | Zbl

[Kolmogorov 1968] A. N. Kolmogorov. Some Theorems on algorithmic entropy and the algorithmic quantity of information. Uspeki Mat. Nauk, Vol. 23:2. 1968. pp. 201.

[Kolmogorov 1983] A. N. Kolmogorov. Combinatorial foundations of information theory and the calculus of probabilities. Russian Mathematical Surveys. Vol. 38.4. 1983. pp. 29-40. | MR | Zbl

[Kolmogorov 1983] A. N. Kolmogorov. On logical foundations of probability theory. In "Probability Theory and Mathematical Statistics. Lecture Notes in Mathematics." Ed. K. Ito and J. V. Prokhorov. Vol. 1021. Springer-Verlag., Berlin. 1983. pp. 1-5. | MR | Zbl

[Kolmogorov Uspenskii 1987] A.N. Kolmogorov and V. A. Uspenskii. Algorithms and Randomness. SIAM Theory Probab. Appl. Vol. 32. 1987. pp. 389-412. | MR | Zbl

[Levin 1973] L. A. Levin. On the notion of random sequence. Dokl. Akad. Nauk SSSR. 212, 3. 1973. | MR | Zbl

[Levin 1974] L. A. Levin. Laws of information conservation (non-growth) and aspects of the foundation of probability theory. Problems Inform. Transmission. 10 n°3. 1974. pp. 206-210. | MR | Zbl

[Levin 1976a] L. A. Levin. On the principle of conservation of information in intuitionistic mathematics. Dokl. Akad. Nauk. SSSR. Tom 227 n°6. 1976. | MR | Zbl

L. A. Levin. On the principle of conservation of information in intuitionistic mathematics. Soviet Math. Dokl. 17 n°2. 1976. pp. 601-605. | MR | Zbl

[Levin 1976b] L. A. Levin. Various measures of complexity for finite objects (axiomatic descriptions). Soviet Math. Dokl. 17. n°2. 1976. pp. 552-526. | MR | Zbl

[Levin 1976c] L. A. Levin. Uniform tests of randomness. Soviet Math. Dokl. 17, n°2. 1976. pp. 337-340. | MR | Zbl

[Levin 1984] L. A. Levin. Randomness conservative inequalities: Information and independence in mathematical theories. Inf. Contr. 61. 1984. pp. 15-37. | MR | Zbl

[Levin 1985] L. A. Levin. One-way function and pseudorandom generators. In "Proceedings of the 17th ACM Symposium on Theory of Computing". 1985. pp. 363-365. | Zbl

[Levin 1989] L. A. Levin. Lettre à l'auteur au sujet des aspects historiques de la théorie algorithmique de l'information. Novembre 1989.

[Levin V'Yugin 1977] L. A. Levin and V. V. V'Yugin. Invariant Properties of Informational Bulks. Lecture Notes in Computer Science n°53. Springer, Berlin. 1977. pp. 359-364. | MR | Zbl

[Li Vitanyi 1989a] M. Li, P. M. B. Vitanyi. A New Approach to Formal Language Theory by Kolmogorov Complexity. Proc 16th International Colloquium on Automata Languages and Programming. 1989. | Zbl

[Li Vitanyi 1989b] M. Li, P. M. B. Vitanyi. Inductive Reasoning and Kolmogorov Complexity. Proc. 4th Annual IEEE Structure in Complexity Theory Conference. 1989. | Zbl

[Li Vitanyi 1990] M. Li, P. M. B. Vitanyi. Kolmogorov Complexity and Its Applications. Handbook of Theoretical Computer Science. J. van Leeuwen Editor. North-Holland. 1990. pp. 187-254 | MR | Zbl

[Li Vitanyi 1990] M. Li, P. M. B. Vitanyi. Introduction to Kolmogorov Complexity and Its Applications. Addison-Wesley, Reading, Mass. To appear. | MR | Zbl

[Loveland 1964] D. W. Loveland. Recursively Random Sequences. Ph. D. Thesis. N.Y.U. June 1964. | MR

[Loveland 1966a] D. W. Loveland. A new interpretation of the von Mises' Concept of random sequence. Zeitschr. F. Math. Logik und Grundlagen d. Math. Bd12. 1966. pp. 279-294. | MR | Zbl

[Loveland 1966b] D. W. Loveland. The Kleene Hierarchy Classification of Recursively Random Sequences. Trans. Amer. Math. Soc. 125. 1966. pp. 487-510. | MR | Zbl

[Loveland 1968] D. W. Loveland. Minimal Program Complexity Measure. Conference Record ACM Symposium on Theory of Computing. May 1968. pp. 61-65. | Zbl

[Loveland 1969] D. W. Loveland. A variant of the Kolmogorov concept of complexity. Information and Control. 15. 1969. pp. 510-526. | MR | Zbl

[Martin-Löf 1966] P. Martin-Löf. On the Concept of a Random Sequence. Theory Probability Appl.. Vol. 11 1966. pp. 177-179

[Martin-Löf 1966] P. Martin-Löf. The Definition of Random Sequences. Information and Control. 9. 1966. pp. 602-619. | MR | Zbl

[Martin-Löf 1969a] P. Martin-Löf. Algorithms and Randomness. Intl. Stat. Rev. 37, 265. 1969. pp. 265-272. | Zbl

[Martin-Löf 1969b] P. Martin-Löf. The Literature on von Mises' Kollektivs Revisited. Theoria, XXXV. 1969. pp. 12-37. | MR | Zbl

[Martin-Löf 1970] P. Martin-Löf. On the notion of Randomness. in "Intuitionism and Proof Theory". A. Kino, J. Myhill and R.E. Vesley, eds. North-Holland Publishing Co. Amsterdam. 1970, pp.73-78. | MR | Zbl

[Martin-Löf 1971] P. Martin-Löf. Complexity Oscillations in Infinite Binary Sequences. Zeitschrift fur Wahrscheinlichkeitstheory und Vervandte Gebiete. 19. 1971. pp.225-230. | MR | Zbl

[Martin-Löf 1974] P. Martin-Löf. The notion of redundancy and its use as a quantitative measure of the discrepancy between statistical hypothesis and a set of observational data. Scand. J. Stat. Vol 1. 1974. pp. 3-18. | MR | Zbl

[Martin-Löf 1975] P. Martin-Löf. Reply to Sverdrup's polemical article "Tests without power". Scand. J. Stat. Vol. 2. 1975. pp. 161-165. | MR | Zbl

[Minsky 1961] M. L. Minsky. Steps towards Artificial Intelligence. Proceedings I.R.E. 1961. pp. 8-30. | MR

[Minsky 1962] M. L. Minsky. Problems of Formulation for Artificial Intelligence. Mathematical Problems in Biological Sciences. Proceedings of Symposia in Applied Mathematics XIV. R.E. Bellmann ed. American Math. Soc. Providence. RI. 1962. | Zbl

[O'Connor 1988] M. O'Connor. An Unpredictibility Approach to Finite-State Randomness. Journal of Computer and System Sciences. 37. 1988 pp. 324-336. | MR | Zbl

[Popper 1935] K. R. Popper. Logik der Forschung. Springer. 1935. Traduction Française: La Logique de la Découverte Scientifique. Payot, Paris. 1978.

[Schnorr 1971a] C. P. Schnorr. A unified approach to the definition of random sequence. Math. Systems Theory. 5. 1971. pp. 246-258. | MR | Zbl

[Schnorr 1971b] C. P. Schnorr. Optimal Gödel numberings. Proc. IFIP Congres 1971. Ljubljana, Yugoslavia. TA-2. pp. 12-24. | Zbl

[Schnorr 1971c] C. P. Schnorr. Zufälligkeit und Wahrscheinlichkeit. Lecture Notes in Mathemathics. Vol 218. Berlin-Heidelberg-New York. Springer, 1971. | MR | Zbl

[Schnorr 1972] C. P. Schnorr. The process complexity and effective random tests. Proc. ACM Conf. on Theory of Computing. 1972. pp. 168-176. | MR | Zbl

[Schnorr 1973] C. P. Schnorr. Process complexity and effective random tests. J. Comput. Syst. Sci. 7. 1973. pp 376-388. | MR | Zbl

[Schnorr 1977] C. P. Schnorr. A survey of the theory of random sequences. In "Basic Problems in Mathodology and Linguistics." Ed. R. E. Butts, J. Hintikka. D. Reidel, Dordrecht. 1977. pp. 193-210. | MR

[Schnorr 1989] C. P. Schnorr. Lettre à l'auteur au sujet des aspects historiques de la théorie algorithmique de l'information. Septembre 1989.

[Shannon Weaver 1949] C.E. Shannon and W. Weaver. The Mathematical Theory of Communication. Univ. of Illinois Press, Urbana, 1949. | MR | Zbl

[Shen' 1983] A. Kh. Shen'. The concept of $(\alpha ,\beta )$-stochasticity in the Kolmogorov sense, and its properties. Soviet Math. Dokl. Vol. 28. 1983. pp. 295-299. | Zbl

[Shen' 1989] A. Kh. Shen'. On relation between different algorithmic definitions of randomness. Soviet Math. Dokl. Vol. 38. 1989. pp. 316-319. | MR | Zbl

[Solomonoff 1960] R. J. Solomonoff. A preliminary report on a general theory of inductive inference. Tech. Rep. ZTB-138. Zator Company. Cambridge, Mass. November 1960.

[Solomonoff 1964] R.J. Solomonoff. A formal theory of inductive Inference. Information and Control. 7. 1964. pp. 1-22. | MR | Zbl

[Solomonoff 1978] R. J. Solomonoff. Complexity-based induction systems: comparisons and convergence theorems. IEEE Transaction on Information Theory. IT-24. 1978. pp. 422-432. | MR | Zbl

[Turing 1936] A. M. Turing. On Computable Numbers, with an application to the Entscheidungsproblem. Proceeding of the London Mathematical Society. 2, 42, 1936-7. pp. 230-265. corrections 43. 1937. pp. 544-546. | JFM | MR | Zbl

[van Lambalgen 1987a] M. Van Lambalgen. Random sequences. Ph. D. Thesis Department of Mathematics, University of Amsterdam, 1987.

[van Lambalgen 1987b] M. Van Lambalgen. Von Mises' definition of random sequences reconsidered. The Journal of Symbolic Logic. 52. 1987. pp. 725-755. | MR | Zbl

[van Lambalgen 1989] M. Van Lambalgen. Algorithmic Information Theory. The Journal of Symbolic Logic. 54 n°4, 1989. pp. 1389-1400. | MR | Zbl

[van Lambalgen 1990] M. Van Lambalgen. The axiomatization of randomness. The Journal of Symbolic Logic. 55. 1990. pp. 1143-1167. | MR | Zbl

[Ville 1936] J. Ville. Sur la notion de collectif. C.R. Acad. Scien. Paris. 203. 1936. pp. 26-27. | JFM

J. Ville. Sur les suites indifférentes. C.R. Acad. Scien. Paris. 202. 1936. p.1393 | JFM

[Ville 1939] J. Ville. Etude critique de la notion de collectif. Gauthier-Villars. Paris. 1939. | Zbl

[von Mises 1919] R. Von Mises. Grundlagen der Wahrscheinlichkietsrechnung. Math. Z. 5. 100. 1919. | JFM

[von Mises 1941] R. Von Mises. On the foundation of probability and statistics. Am. Math. Statist. 12. 1941. pp.191-205. | MR | Zbl

[von Mises 1964] R. Von Mises. Selected papers of Richard von Mises. Providence, Rhode Island, Amer. Math. Soc. 1964. | MR | Zbl

[von Mises Geiringer 1964] R. Von Mises, H. Geiringer. Mathematical Theory of Probability and Statistics. Academic Press, New-York and London. 1964. | MR | Zbl

[Wald 1936] A. Wald. Sur la notion de collectif dans le calcul des probabilités. C. R. Acad. Sc. Paris. 202. 1936. pp. 180-183. | JFM

[Wald 1937] A. Wald. Die Widerspruchsfreiheit des Kollektivbegriffes der Wahrscheinlichkeitsrechnung. Ergebnisse eines Mathetischen Kolloquiums. 8. 1937. pp. 38-72. | JFM | Zbl

[Wald 1938] A. Wald. Die Widerspruchsfreiheit des Kollektivgriffes. Actualités Sci. Indust. 735. 1938. pp. 79-99. | JFM

[Zvonkin Levin 1970] A.K. Zvonkin, L.A. Levin. The Complexity of finite object and the development of the concepts of information and randomness by means of the theory of algorithms. Russ. Math. Survey. 25, 6. 1970. pp 83-124. | MR | Zbl