Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-22T21:54:51.553Z Has data issue: false hasContentIssue false
  • English
  • Français

ON ANALOGUES OF THE CHURCH–TURING THESIS IN ALGORITHMIC RANDOMNESS

Published online by Cambridge University Press:  14 July 2016

CHRISTOPHER P. PORTER
Get access Rights & Permissions [Opens in a new window]

Abstract

In this article, I consider the status of several statements analogous to the Church–Turing thesis that assert that some definition of algorithmic randomness captures the intuitive conception of randomness. I argue that we should not only reject the theses that have appeared in the algorithmic randomness literature, but more generally that we ought not evaluate the adequacy of a definition of randomness on the basis of whether it captures the so-called intuitive conception of randomness to begin with. Instead, I argue that a more promising alternative is to evaluate the adequacy of a definition of randomness on the basis of whether it captures what I refer to as a “notion of almost everywhere typicality.” In support of my main claims, I will appeal to recent work in showing the connection between of algorithmic randomness and certain “almost everywhere” theorems from classical mathematics.

Type
Research Article
Information
The Review of Symbolic Logic , Volume 9 , Issue 3 , September 2016 , pp. 456 - 479
Copyright
Copyright © Association for Symbolic Logic 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

BIBLIOGRAPHY

Bar-Hillel, M. & Wagenaar, W. A. (1991). The perception of randomness. Advances in Applied Mathematics, 12(4), 428–454.CrossRefGoogle Scholar
Bienvenu, L., Day, A. R., Hoyrup, M., Mezhirov, I., & Shen, A. (2012). A constructive version of Birkhoff’s ergodic theorem for Martin-Löf random points. Information and Computation, 210, 21–30.CrossRefGoogle Scholar
Boolos, G. S., Burgess, J. P., & Jeffrey, R. C. (2007). Computability and Logic (fifth edition). Cambridge: Cambridge University Press.CrossRefGoogle Scholar
Brattka, V., Miller, J. S., & Nies, A. (2016). Randomness and differentiability. Transactions of the American Mathematical Society, 368(1), 581–605.CrossRefGoogle Scholar
Dasgupta, A. (2011). Mathematical foundations of randomness. In Bandyopadhyay, P. S., Forster, M. R., and Gabbay, Dov M., editors. Handbook of the Philosophy of Statistics. Amsterdam: North Holland, pp. 641–712.CrossRefGoogle Scholar
Delahaye, J.-P. (2011). The Martin-Löf-Chaitin Thesis: The identification by recursion theory of the mathematical notion of random sequence. In Zenil, H., editor. Randomness Through Computation. Hackensack, NJ: World Scientific Publishing Company, pp. 121–140.CrossRefGoogle Scholar
Demuth, O. (1975). The differentiability of constructive functions of weakly bounded variation on pseudo numbers. Commentationes mathematicae Universitatis Carolinae, 16(3), 583–599.Google Scholar
Eagle, A. (2014). Chance versus Randomness. The Stanford Encyclopedia of Philosophy (Spring 2014 Edition), In Zalta, E. N., editor, http://plato.stanford.edu/archives/spr2014/entries/chance-randomness.Google Scholar
Ershov, Yu. L., Goncharov, S. S., Nerode, A., Remmel, J. B., & Marek, V. W., editors. (1998). Handbook of Recursive Mathematics, Vol. 1. Studies in Logic and the Foundations of Mathematics, Vol. 138. Amsterdam: North-Holland. Recursive model theory.Google Scholar
Ershov, Yu. L., Goncharov, S. S., Nerode, A., Remmel, J. B., & Marek, V. W., editors. (1998). Handbook of Recursive Mathematics, Vol. 2. Studies in Logic and the Foundations of Mathematics, Vol. 139. Amsterdam: North-Holland. Recursive algebra, analysis and combinatorics.Google Scholar
Falk, R. & Konold, C. (1997). Making sense of randomness: Implicit encoding as a basis for judgment. Psychological Review, 104(2), 301.CrossRefGoogle Scholar
Franklin, J. N. Y., Greenberg, N., Miller, J. S., & Ng, K. M. (2012). Martin-Löf random points satisfy Birkhoff’s ergodic theorem for effectively closed sets. Proceedings of the American Mathematical Society, 140(10), 3623–3628.CrossRefGoogle Scholar
Gaifman, H. & Snir, M. (1982). Probabilities over rich languages, testing and randomness. The Journal of Symbolic Logic, 47(3), 495–548.CrossRefGoogle Scholar
Gödel, K. (1946). Remarks before the princeton bicentennial conference on problems in mathematics. Collected Works, 2, 144–153.Google Scholar
Harizanov, V. S. (1998). Pure computable model theory. In Handbook of Recursive Mathematics, Vol. 1. Studies in Logic and the Foundations of Mathematics, Vol. 138. Amsterdam: North-Holland, pp. 3–114.Google Scholar
Hoyrup, M. (2012). The dimension of ergodic random sequences. In 29th International Symposium on Theoretical Aspects of Computer Science. LIPIcs. Leibniz International Proceedings in Informatics, Vol. 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, pp. 567–576.Google Scholar
Hoyrup, M. & Rojas, C. (2009). An application of Martin-Löf randomness to effective probability theory. In Mathematical Theory and Computational Practice. Lecture Notes in Computer Science, Vol. 5635. Berlin: Springer, pp. 260–269.CrossRefGoogle Scholar
Hoyrup, M. & Rojas, C. (2009). Applications of effective probability theory to Martin-Löf randomness. In Automata, Languages and Programming. Part I. Lecture Notes in Computer Science, Vol. 5555. Berlin: Springer, pp. 549–561.Google Scholar
Kolmogorov, A. N. (1983). Combinatorial foundations of information theory and the calculus of probabilities. Uspekhi Matematicheskikh Nauk, 38(4(232)), 27–36.Google Scholar
Kurtz, S. (1982). Randomness and genericity in the degrees of unsolvability. Dissertation Abstracts International Part B: Science and Engineering [DISS. ABST. INT. PT. B- SCI. & ENG.], 42(9), 1982.Google Scholar
Kuyper, R. & Terwijn, S. A. (2014). Effective genericity and differentiability. Journal of Logic and Analysis, 6, Paper 4, 14.Google Scholar
Martin-Löf, P. (1966). The definition of random sequences. Information and Control, 9, 602–619.CrossRefGoogle Scholar
Miyabe, K. (2013). Characterization of Kurtz randomness by a differentiation theorem. Theory of Computing Systems, 52(1), 113–132.CrossRefGoogle Scholar
Osherson, D. & Weinstein, S. (2008). Recognizing strong random reals, this Review, 1(01), 56–63.CrossRefGoogle Scholar
Pathak, N., Rojas, C., & Simpson, S. G. (2014). Schnorr randomness and the Lebesgue differentiation theorem. Proceedings of the American Mathematical Society, 142(1), 335–349.CrossRefGoogle Scholar
Porter, C. (2012). Mathematical and Philosophical Perspectives on Algorithmic Randomness. Ph.D. Thesis, University of Notre Dame.Google Scholar
Raatikainen, P. (2000). Algorithmic information theory and undecidability. Synthese, 123(2), 217–225.CrossRefGoogle Scholar
Rute, J. (2013). Topics in algorithmic randomness and computable analysis. Ph.D. Thesis, Carnegie Mellon University, p. 81.Google Scholar
Schnorr, C.-P. (1971). A unified approach to the definition of random sequences. Mathematical Systems Theory, 5, 246–258.CrossRefGoogle Scholar
Schnorr, C.-P. (1971). Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. Lecture Notes in Mathematics, Vol. 218. Berlin: Springer-Verlag.Google Scholar
Schnorr, C.-P. (1977). A survey of the theory of random sequences. In Basic Problems in Methodology and Linguistics (Proc. Fifth Internat. Congr. Logic, Methodology and Philos. of Sci., Part III, Univ. Western Ontario, London, Ont., 1975). Dordrecht: Reidel, pp. 193–211. Univ. Western Ontario Ser. Philos. Sci., Vol. 11.Google Scholar
Turing, A. M. (1936). On computable numbers, with an application to the entscheidungsproblem. Proceedings London Mathematical Society, S2-42(1), 230–265.Google Scholar
van Lambalgen, M. (1987). Random sequences. Ph.D. Thesis, University of Amsterdam.Google Scholar
Ville, J. (1939). Étude critique de la notion de collectif, Monographies des Probabilités 3, Paris: Gauthier-Villars.Google Scholar
Wang, Y. (1999). A separation of two randomness concepts. Information Processing Letters, 69(3), 115–118.CrossRefGoogle Scholar