Skip to main content Accessibility help
×
Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-09T05:28:42.891Z Has data issue: false hasContentIssue false

Computability theory, algorithmic randomness and Turing's anticipation

Published online by Cambridge University Press:  05 June 2014

Rod Downey
Affiliation:
Victoria University of Wellington
Rod Downey
Affiliation:
Victoria University of Wellington
Get access

Summary

Abstract. This article looks at the applications of Turing's legacy in computation, particularly to the theory of algorithmic randomness, where classical mathematical concepts such as measure could be made computational. It also traces Turing's anticipation of this theory in an early manuscript.

§1. Introduction. Beginning with the work of Church, Kleene, Post and particularly Turing, especially in the magic year of 1936, we know what computation means. Turing's theory has substantially developed under the names of recursion theory and computability theory. Turing's work can be seen as perhaps the high point in the confluence of ideas in 1936. This paper, and Turing's 1939 paper [141] (based on his PhD Thesis of the same name), laid solid foundations to the pure theory of computation. This article gives a brief history of some of the main lines of investigation in computability theory, a major part of Turing's legacy.

Computability theory and its tools for classifying computational tasks have seen applications in many areas such as analysis, algebra, logic, computer science and the like. Such applications will be discussed in articles in this volume. The theory even has applications into what is thought of as proof theory in what is called reverse mathematics. Reverse mathematics attempts to calibrate the logical strength of theorems of mathematics according to calibrations of comprehension axioms in second order mathematics. Generally speaking most separations, that is, proofs that a theorem is true in one system but not another, are performed in normal “ω” models rather than nonstandard ones.

Type
Chapter
Information
Turing's Legacy
Developments from Turing's Ideas in Logic
, pp. 90 - 123
Publisher: Cambridge University Press
Print publication year: 2014

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

[1] U., Abraham and R., Shore, Initial segments of the turing degrees of size ℵ1, Israel Journal of Mathematics, vol. 55 (1986), pp. 1-51.Google Scholar
[2] K., Ambos-Spies, D., Hirschfeldt, and R., Shore, Undecidability and 1-types in intervals of the c.e. degrees, Annals of Pure and Applied Logic, vol. 106 (2000), pp. 1-48.Google Scholar
[3] Chris, Ash and Julia, Knight, Computable structures and the hyperarithmetical hierarchy, Elsevier, 2000.
[4] K., Athreya, J., Hitchcock, J., Lutz, and E., Mayordomo, Effective strong dimension in algorithmic information and computational complexity, SIAM Journal on Computing, vol. 37 (2007), pp. 671-705.Google Scholar
[5] J., Avigad, The metamathematics of ergodic theory, Annals of Pure and Applied Logic, vol. 157 (2009), pp. 64-76.Google Scholar
[6] G., Barmpalias, A., Lewis, and K. M., Ng, The importance of classes in effective randomness, The Journal of Symbolic Logic, vol. 75 (2010), no. 1, pp. 387-400.Google Scholar
[7] V., Becher, Turing's normal numbers: towards randomness, CiE 2012 (S. B., Cooper, A., Dawar, and B., Löwe, editors), Lecture Notes in Computer Science 7318, Springer, Heidelberg, 2012, pp. 35-45.
[8] V., Becher and S., Figueira, An example of a computable absolutely normal number, Theoretical Computer Science, vol. 270 (2002), pp. 947-958.Google Scholar
[9] V., Becher, S., Figueira, and R., Picchi, Turing's unpublished algorithm for normal numbers, Theoretical Computer Science, vol. 377 (2007), pp. 126-138.Google Scholar
[10] V., Becher and S., Grigorieff, From index sets to randomness in n, Random reals and possibly infinite computations, The Journal of Symbolic Logic, vol. 74 (2009), no. 1, pp. 124-156.Google Scholar
[11] J., Bertrand, Calcul des probabilités, Gauthier-Villars et fils, Paris, 1889.
[12] L., Bienvenu, A., Day, M., Hoyrup, I., Mezhirov, and A., Shen, Ergodic-type characterizations of algorithmic randomness, Information and Computation, (to appear).
[13] L., Bienvenu and R., Downey, Kolmogorov complexity and Solovay functions, Symposium on Theoretical Aspects of Computer Science (STACS 2009), 2009, pp. 147-158.
[14] L., Bienvenu and W., Merkle, Reconciling data compression and Kolmogorov complexity, Proceedings of the 34th International Colloquium on Automata, Languages, and Programming (ICALP 2007), Lecture Notes in Computer Science 4596, Springer, 2007.
[15] L., Bienvenu, An. A., Muchnik, A., Shen, and N., Vereshchagin, Limit complexities revisited, Symposium on Theoretical Aspects of Computer Science (STACS 2008), 2008.
[16] Émil, Borel, Les probabilités denombrables et leurs applications arithmétiques, Rendiconti del Circolo Matematico di Palermo, vol. 27 (1909), pp. 247-271.Google Scholar
[17] Émil, Borel, Leçons sur la thèorie des fonctions, 2nd ed., Gauthier Villars, 1914.
[18] C., Bourke, J., Hitchcock, and N., Vinodchandran, Entropy rates and finite-state dimension, Theoretical Computer Science, vol. 349 (2005), no. 3, pp. 392-406.Google Scholar
[19] V., Brattka, J., Miller, and A., Nies, Randomness and differentiability, to appear.
[20] M., Braverman and M., Yampolsky, Non-computable Julia sets, Journal of the American Mathematical Society, vol. 19 (2006), no. 3.Google Scholar
[21] M., Braverman and M., Yampolsky, Computability of Julia sets, Springer-Verlag, 2008.
[22] Yann, Bugeaud, Nombres de Liouville et nombres normaux, Comptes Rendus de l'Academie des Sciences de Paris, vol. 335 (2002), pp. 117-120.Google Scholar
[23] Yann, Bugeaud, Distribution modulo one and diophantine approximation, Cambridge University Press, 2012.
[24] Douglas, Cenzer and Carl, Jockusch, classes—structure and applications, Contemporary Mathematics, vol. 257 (2000), pp. 39-59.Google Scholar
[25] G., Chaitin, A theory of program size formally identical to information theory, Journal of the ACM, vol. 22 (1975), pp. 329-340.Google Scholar
[26] G., Chaitin, Information-theoretical characterizations of recursive infinite strings, Theoretical Computer Science, vol. 2 (1976), pp. 45-48.Google Scholar
[27] P., Cholak, R., Downey, and N., Greenberg, Strong-jump traceablilty. I. The computably enumerable case, Advances in Mathematics, vol. 217 (2008), pp. 2045-2074.Google Scholar
[28] Peter, Cholak, Rod, Downey, and Leo, Harrington, On the orbits of computably enumerable sets, Journal of the American Mathematical Society, vol. 21 (2008), no. 4, pp. 1105-1135.Google Scholar
[29] Peter, Cholak and Leo, Harrington, On the definability of the double jump in the computably enumerable sets, Journal of Mathematical Logic, vol. 2 (2002), no. 2, pp. 261-296.Google Scholar
[30] Alonzo, Church, On the concept of a random sequence, Bulletin of the American Mathematical Society, vol. 46 (1940), pp. 130-135.Google Scholar
[31] R., Cilibrasi, P. M. B., Vitanyi, and R., de Wolf, Algorithmic clustering of music based on string compression, Computer Music Journal, vol. 28 (2004), pp. 49-67.Google Scholar
[32] C., Conidis, A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one, The Journal of Symbolic Logic, vol. 77 (2012), no. 2, pp. 447-474.Google Scholar
[33] Barry, Cooper, Minimal degrees and the jump operator, The Journal of Symbolic Logic, vol. 38 (1973), pp. 249-271.Google Scholar
[34] Barry, Cooper, Minimal pairs and high recursively enumerable degrees, The Journal of Symbolic Logic, vol. 39 (1974), pp. 655-660.Google Scholar
[35] L., Dai, J., Lutz, and E., Mayordomo, Finite-state dimension, Theoretical Computer Science, vol. 310 (2004), pp. 1-33.Google Scholar
[36] Martin, Davis, Computability and unsolvability, Dover, 1985.
[37] K., de Leeuw, E. F., Moore, C. E., Shannon, and N., Shapiro, Computability by probabilistic machines, Automata studies (C. E., Shannon and J., McCarthy, editors), Annals of Mathematics Studies 34, Princeton University Press, Princeton, NJ, 1956, pp. 183-212.
[38] O., Demuth, The differentiability of constructive functions of weakly bounded variation on pseude-numbers, Commentationes Mathematicae Universitatis Carolinae, vol. 16 (1975), pp. 583-599.Google Scholar
[39] R., Downey, Lattice nonembeddings and initial segments of the recursively enumerable degrees, Annals of Pure and Applied Logic, vol. 49 (1990), pp. 97-119.Google Scholar
[40] R., Downey, Algorithmic randomness and computability, Proceedings of the 2006 International Congress of Mathematicians, vol. 2, European Mathematical Society, 2006, pp. 1-26.
[41] R., Downey, Five lectures on algorithmic randomness, Computational prospects of infinity, Part I: Tutorials (C., Chong, Q., Feng, T. A., Slaman, W. H., Woodin, and Y., Yang, editors), Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, vol. 14, World Scientific, Singapore, 2008, pp. 3-82.
[42] R., Downey, J., Flum, M., Grohe, and M., Weyer, Bounded fixed-parameter tractability andreducibility, Annals of Pure and Applied Logic, vol. 148 (2007), pp. 1-19.Google Scholar
[43] R., Downey and N., Greenberg, A transfinite hierarchy of computably enumerable degrees, unifying classes, and natural definability, monograph, in preparation.
[44] R., Downey and N., Greenberg, Pseudo-jump operators and SJTHard sets, Advances in Mathematics, (to appear).
[45] R., Downey and D., Hirschfeldt, Algorithmic randomness and complexity, Springer-Verlag, 2010.
[46] R., Downey, D., Hirschfeldt, A., Nies, and S., Terwijn, Calibrating randomness, The Bulletin of Symbolic Logic, vol. 12 (2006), pp. 411-491.Google Scholar
[47] R., Downey, A., Nies, R., Weber, and L., Yu, Lowness and nullsets, The Journal of Symbolic Logic, vol. 71 (2006), pp. 1044-1052.Google Scholar
[48] R., Downey and R., Shore, Lattice embeddings below a non-low2 recursively enumerable degree, Israel Journal of Mathematics, vol. 94 (1996), pp. 221-246.Google Scholar
[49] R., Downey and R., Shore, There is no degree invariant half-jump, Proceedings of the American Mathematical Society, vol. 125 (1997), pp. 3033-3037.Google Scholar
[50] Rod, Downey, Randomness, computation and mathematics, CiE 2012 (S. B., Cooper, A., Dawar, and B., Löwe, editors), Lecture Notes in Computer Science 7318, Springer, Heidelberg, 2012.
[51] Rachel, Epstein, The nonlow computably enumerable degrees are not invariant in E, Transactions of the American Mathematical Society, (to appear).
[52] Lawrence, Feiner, The strong homogeneity conjecture, The Journal of Symbolic Logic, vol. 35 (1970), pp. 373-377.Google Scholar
[53] L., Fortnow, J., Hitchcock, P., Aduri, V., Vinochandran, and F., Wang, Extracting Kolmogorov complexity with applications to dimension zero-one laws, Proceedings of the 33rd International Colloquium on Automata, Languages, and Programming (ICALP 2006), Lecture Notes in Computer Science 4051, Springer, 2006, pp. 335-345.
[54] W., FOUCHE, The descriptive complexity of Brownian motion, Advances in Mathematics, vol. 155 (2000), pp. 317-343.Google Scholar
[55] W., FOUCHE, Dynamics of a generic Brownian motion: Recursive aspects, Theoretical Computer Science, vol. 394 (2008), pp. 175-186.Google Scholar
[56] J., Franklin, N., Greenberg, J., Miller, and Keng Meng, Ng, Martin-Löf random points satisfy Birkhoff's ergodic theorem for effectively closed sets, Proceedings of the American Mathematical Society, (to appear).
[57] R., Friedberg, A criterion for completeness of degrees of unsolvability, The Journal of Symbolic Logic, vol. 22 (1957), pp. 159-160.Google Scholar
[58] R., Friedberg, Two recursively enumerable sets of incompatible degrees of unsolvability, Proceedings of the National Academy of Sciences of the United States of America, vol. 43 (1957), pp. 236-238.Google Scholar
[59] H., Fuchs and C., Schnorr, Monte Carlo methods and patternless sequences, Operations Research Verfahren XXV, Symposium Heidelberg, 1977, pp. 443-450.
[60] P., Gács, On the relation between descriptional complexity and algorithmic probability, Theoretical Computer Science, vol. 22 (1983), pp. 71-93.Google Scholar
[61] P., Gács, Every set is reducible to a random one, Information and Control, vol. 70 (1986), pp. 186-192.Google Scholar
[62] P., Gács, M., Hoyrup, and C., Rojas, Randomness on computable probability spaces, a dynamical point of view, Theory of Computing Systems, (to appear).
[63] S., Gregorieff and M., Ferbus, Is randomness native to computer science? Ten years after, In Zenil[152],pp. 243-263.
[64] E., Griffor, Handbook of computability theory, Elsevier, 1999.
[65] Marcia J., Groszek and Theodore A., Slaman, Independence results on the global structure of the Turing degrees, Transactions of the American Mathematical Society, vol. 277 (1983), no. 2, pp. 579-588.Google Scholar
[66] G. H., Hardy and E. M., Wright, An introduction to the theory of numbers, Oxford University Press, 1979, first edition in 1938.
[67] Leo, Harrington, Maclachlin's conjecture, handwritten notes 1970s.
[68] Leo, Harrington and Robert, Soare, Post's Program and incomplete recursively enumerable sets, Proceedings of the National Academy of Sciences of the United States of America, vol. 88 (1991), pp. 10242-10246.Google Scholar
[69] Rolf, Herken, The universal Turing Machine: A half-century survey, Springer-Verlag, 1995.
[70] M., Hochman and T., Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type, Annals of Mathematics, vol. 171 (2010), no. 3, pp. 2011-2038.Google Scholar
[71] R., Hölzl, T., Kräling, and W., Merkle, Time bounded Kolmogorov complexity and Solovay functions, Mathematical Foundations of Computer Science 2009, Lecture Notes in Computer Science, vol. 5734, Springer, 2009, pp. 392-402.
[72] Carl, Jockusch and Robert, Soare, Degrees of members of classes, Pacific Journal of Mathematics, vol. 40 (1972), pp. 605-616.Google Scholar
[73] B., Kjos-Hanssen, W., Merkle, and F., Stephan, Kolmogorov complexity and the recursion theorem, Symposium on Theoretical Aspects of Computer Science (STACS 2006), Lecture Notes in Computer Science 3884, Springer, 2006, pp. 149-161.
[74] B., Kjos-Hanssen and A., Nerode, Effective dimension of points visited by Brownian motion, Theoretical Computer Science, vol. 410 (2009), no. 4–5, pp. 347-354.Google Scholar
[75] B., Kjos-Hanssen and T., Szabados, Kolmogorov complexity and strong approximation of Brownian motion, Proceedings of the American Mathematical Society, vol. 139 (2011), no. 9, pp. 3307-3316.Google Scholar
[76] Stephen, Kleene and Emil, Post, The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics, vol. 59 (1954), no. 3, pp. 379-407.Google Scholar
[77] A. N., Kolmogorov, Three approaches to the quantitative definition of information, Problems of Information Transmission, vol. 1 (1965), pp. 1-7.Google Scholar
[78] A., Kučera, Measure, classes, and complete extensions of PA, Recursion Theory Week: Proceedings, Oberwolfach, 1984, Lecture Notes in Mathematics, vol. 1141, Springer, Berlin, 1985, pp. 245-259.
[79] A., Kučera and T., Slaman, Randomness and recursive enumerability, SIAM Journal on Computing, vol. 31 (2001), pp. 199-211.Google Scholar
[80] A., Lachlan, Lower bounds for pairs of recursively enumerable degrees, Proceedings of the London Mathematical Society, vol. 16 (1966), pp. 537-569.Google Scholar
[81] A., Lachlan, Uniform enumeration operators, The Journal of Symbolic Logic, vol. 40 (1975), pp. 401-409.Google Scholar
[82] A. H., Lachlan, Embedding nondistributive lattices in the recursively enumerable degrees, Proceedings of the Conference in Mathematical Logic—London '70, (Bedford College, London, 1970), Lecture Notes in Mathematics, vol. 255, Springer, Berlin, 1972, pp. 149-177.
[83] A. H., Lachlan and R., Soare, Not every finite lattice is embeddable in the recursively enumerable degrees, Advances in Mathematics, vol. 37 (1980), pp. 74-82.Google Scholar
[84] Henri, Lebesgue, Sur certaines demonstrations d'existence, Bulletin de la Société Mathematique de France, vol. 45 (1917), pp. 132-144.Google Scholar
[85] Steffen, Lempp and Manuel, Lerman, The decidability of the existential theory of the poset of the recursively enumerable degrees with jumprelations, Advances in Mathematics, (1996).
[86] Steffen, Lempp, A finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees, Annals of Pure and Applied Logic, vol. 87 (1997), no. 2, pp. 167-185, Logic Colloquium '95 Haifa.Google Scholar
[87] Manuel, Lerman, Degrees of unsolvability: Local and global theory, Springer-Verlag, 1983.
[88] Manuel, Lerman, The embedding problem for the recursively enumerable degrees, Recursion theory (Ithaca, NY, 1982), Proceedings of the Symposia in Pure Mathematics, vol. 42, American Mathematical Society, Providence, RI, 1985, pp. 13-20.
[89] L., Levin, Some theorems on the algorithmic approach to probability theory and information theory, Dissertation in Mathematics, Moscow University, 1971.
[90] L., Levin, Laws of information conservation (non-growth) and aspects of the foundation of probability theory, Problems of Information Transmission, vol. 10 (1974), pp. 206-210.Google Scholar
[91] M. B., Levin, On absolutely normal numbers, Moscow University Mathematics Bulletin, vol. 34 (1979), pp. 32-39, English translation.Google Scholar
[92] P., Lévy, Théorie de l'addition des variables aléatoires, Gauthier-Villars, 1937.
[93] Angus, Macintyre, Transfinite iterations of Friedberg's completeness criterion, The Journal of Symbolic Logic, vol. 38 (1977), pp. 1-10.Google Scholar
[94] David, Marker, Degrees of models of true arithmetic, Proceedings Herbrand Symposio (J., Stern, editor), North-Holland, Amsterdam, 1982, pp. 233-242.
[95] D. A., Martin, Classes of recursively enumerable sets and degrees of unsolvability, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 12 (1966), pp. 295-310.Google Scholar
[96] P., Martin-Löf, The definition of random sequences, Information and Control, vol. 9 (1966), pp. 602-619.Google Scholar
[97] E., Mayordomo, A Kolmogorov complexity characterization of constructive Hausdorff dimension, Information Processing Letters, vol. 84 (2002), pp. 1-3.Google Scholar
[98] J., Miller, Kolmogorov random reals are 2-random, The Journal of Symbolic Logic, vol. 69 (2004), no. 3, pp. 907-913.Google Scholar
[99] J., Miller, The K-degrees, low for K-degrees, and weakly low for K sets, Notre Dame Journal of Formal Logic, vol. 50 (2010), no. 4, pp. 381-391.Google Scholar
[100] J., Miller, Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension, Advances in Mathematics, vol. 226 (2011), no. 1, pp. 373-384.Google Scholar
[101] J. S., Miller and L., Yu, On initiai segment complexity and degrees of randomness, Transactions of the American Mathematical Society, vol. 360 (2008), no. 6, pp. 3193-3210.Google Scholar
[102] A., Muchnik, On the unsolvability of the problem of reducibility in the theory of algorithms, Doklady Akademii Nauk SSSR, vol. 106 (1956), pp. 194-197.Google Scholar
[103] An. A., Muchnik, A., Semenov, and V., Uspensky, Mathematical metaphysics of randomness, Theoretical Computer Science, vol. 207 (1998), no. 2, pp. 263-317.Google Scholar
[104] J., Myhill, Creative sets, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 1 (1955), pp. 97-108.Google Scholar
[105] A., Nies, Lowness properties and randomness, Advances in Mathematics, vol. 197 (2005), no. 1, pp. 274-305.Google Scholar
[106] A., Nies, Computability and randomness, Oxford University Press, 2009.
[107] A., Nies, Interactions of computability and randomness, Proceedings of the International Congress of Mathematicians (S., Ragunathan, editor), 2010, pp. 30-57.
[108] A., Nies, R., Shore, and T., Slaman, Interpretability and definability in the recursively enumerable degrees, Proceedings of the London Mathematical Society, vol. 77 (1998), pp. 241-291.Google Scholar
[109] A., Nies, F., Stephan, and S. A., Terwijn, Randomness, relativization, and Turing degrees, The Journal of Symbolic Logic, vol. 70 (2005), no. 2, pp. 515-535.Google Scholar
[110] P., Odifreddi, Classical recursion theory, vol. 1, North-Holland, 1989.
[111] P., Odifreddi, Classical recursion theory, vol. 2, North-Holland, 1999.
[112] Emil, Post, Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, vol. 50 (1944), no. 5, pp. 284-316.Google Scholar
[113] M., Pour-El and I., Richards, Computability in analysis and physics, Springer-Verlag, 1989.
[114] J., Reimann, Effectively closed classes of measures and randomness, Annals of Pure and Applied Logic, vol. 156 (2008), no. 1, pp. 170-182.Google Scholar
[115] J., Reimann and T., Slaman, Randomness for continuous measures, (draft available from Reimann's web site), to appear.
[116] Robert, Robinson, Jump restricted interpolation in the recursively enumerable degrees, Annals of Mathematics, vol. 93 (1971), no. 3, pp. 586-596.Google Scholar
[117] Hartley, Rogers Jr., Theory of recursive functions and effective computabilty, McGraw-Hill, 1967.
[118] Gerald, Sacks, The recursively enumerable degrees are dense, Annals of Mathematics, vol. 80 (1964), pp. 300-312.Google Scholar
[119] W. M., Schmidt, On normal numbers, Pacific Journal of Mathematics, vol. 10 (1960), pp. 661-672.Google Scholar
[120] C. P., Schnorr, A unified approach to the definition of a random sequence, Mathematical Systems Theory, vol. 5 (1971), pp. 246-258.Google Scholar
[121] C. P., Schnorr, Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie, Lecture Notes in Mathematics, vol. 218, Springer-Verlag, Berlin-New York, 1971.
[122] C. P., Schnorr and H., Stimm, Endliche Automaten und Zufallsfoigen, Acta Informatica, vol. 1 (1972), pp. 345-359.Google Scholar
[123] Richard, Shore, The homogeneity conjecture, Proceedings of the National Academy of Sciences of the United States of America, vol. 76 (1979), pp. 4218-4219.Google Scholar
[124] Richard, Shore, On homogeneity and definability in the first order theory of the Turing degrees, The Journal of Symbolic Logic, vol. 47 (1982), pp. 8-16.Google Scholar
[125] Richard, Shore, A non-inversion theorem for the jump operator, Annals of Pure and Applied Logic, vol. 40 (1988), pp. 277-303.Google Scholar
[126] Richard, Shore and Theodore, Slaman, Defining the Turing jump, Mathematical Research Letters, vol. 6 (1999), pp. 711-722.Google Scholar
[127] Waclaw, Sierpiński, Démonstration élémentaire du théorème de M. Borelsur les nombres absolument normaux et détermination effective d'un telnombre, Bulletin de la Société Mathématique de France, vol. 45 (1917), pp. 127-132.Google Scholar
[128] S., Simpson, Symbolic dynamics: Entropy = dimension = complexity, preprint (16 December 2011) submitted.
[129] S., Simpson, Mass problems associated with effectively closed sets, Tohoku Mathematical Journal, vol. 63 (2011), pp. 489-517.Google Scholar
[130] S., Simpson, Medvedev degrees of 2-dimensional subshifts of finite type, Ergodic Theory and Dynamical Systems, (to appear), published online 29 November 2012, http://dx.doi.org/10.1017/etds.2012.152.
[131] Theodore, Slaman and John, Steel, Definable functions on degrees, Cabal seminar 81–85, Lecture Notes in Mathematics, vol. 1333, Springer, Berlin, 1988, pp. 37-55.
[132] Theodore A., Slaman, The density of infima in the recursively enumerable degrees, Annals of Pure and Applied Logic, vol. 52 (1991), no. 1–2, pp. 155-179.Google Scholar
[133] Theodore A., Slaman, Global properties of the Turing degrees and the Turing jump, Computational prospects of infinity. Part I. Tutorials, Lecture Notes Series. Institute for Mathematical Sciences. National University of Singapore, vol. 14, World Science Publishing, Hackensack, NJ, 2008, pp. 83-101.
[134] Robert, Soare, Automorphisms of the lattice of recursively enumerable sets I: maximal sets, Annals of Mathematics, vol. 100 (1974), pp. 80-120.Google Scholar
[135] Robert, Soare, Recursively enumerable sets and degrees, Springer-Verlag, 1987.
[136] Clifford, Spector, On the degrees of recursive unsolvability, Annals of Mathematics, vol. 64 (1956), pp. 581-592.Google Scholar
[137] F., Stephan, Martin-Löfrandom sets and PA-complete sets, Logic Colloquium '02, Lecture Notes in Logic, vol. 27, Association for Symbolic Logic, 2006, pp. 342-348.
[138] Martin, Strauss, Normal numbers and sources for BPP, Theoretical Computer Science, vol. 178 (1997), pp. 155-169.Google Scholar
[139] S., Terwijn and D., Zambella, Algorithmic randomness and lowness, The Journal of Symbolic Logic, vol. 66 (2001), pp. 1199-1205.Google Scholar
[140] A., Turing, On computable numbers with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, vol. 42 (1936), pp. 230-265, correction in Proceedings of the London Mathematical Society, vol. 43 (1937), pp. 544–546.Google Scholar
[141] A., Turing, Systems of logic based on ordinals, Proceedings of the London Mathematical Society. Second Series, vol. 45 (1939), pp. 161-228.Google Scholar
[142] A., Turing, Computing machinery and intelligence, Mind, vol. 59 (1950), pp. 433-460.Google Scholar
[143] A., Turing, A note on normal numbers, Collected works of A. M. Turing: Pure mathematics (J. L., Britton, editor), North Holland, Amsterdam, 1992, with notes of the editor in pp. 263-265, pp. 117–119.
[144] J., Ville, Étude critique de la notion de collectif, Gauthier-Villars, 1939.
[145] P., Vitanyi, Information distance in multiples, Institute of Electrical and Electronics Engineers. Transactions on Information Theory, vol. 57 (2011), no. 4, pp. 2451-2456.Google Scholar
[146] R., von Mises, Grundlagen der Wahrscheinlichkeitsrechnung, Mathematische Zeitschrift, vol. 5 (1919), pp. 52-99.Google Scholar
[147] J., von Neumann, Various techniques used in connection with random digits, Monte Carlo methods (A. S., Householder, G. E., Forsythe, and H. H., Germond, editors), National Bureau of Standards Applied Mathematics Series, vol. 12, 1951, pp. 36-38.
[148] A., Wald, Sur la notion de collectif dans le calcul des probabilités, Comptes Rendus des Séances de l'Académie des Sciences, vol. 202 (1936), pp. 1080-1083.Google Scholar
[149] A., Wald, Die Weiderspruchsfreiheit des Kollektivbegriffes der Wahrscheinlichkeitsrechnung, Ergebnisse eines mathematischen Kolloquiums, vol. 8 (1937), pp. 38-72.Google Scholar
[150] B., Weinstein, On embeddings of the 1–3–1 lattice into the recursively enumerable degrees, Ph.D. thesis, University of California, Berkeley, 1988.
[151] C., Yates, A minimal pair of recursively enumerable degrees, The Journal of Symbolic Logic, vol. 31 (1966), no. 2, pp. 159-168.Google Scholar
[152] Hector, Zenil(editor), Randomness through computation: Some answers, more questions, World Scientific, Singapore, 2011.
[153] M., Zimand, Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences, Computer science—theory and applications (E., Hirsch, A., Razborov, A., Semenov, and A., Slissenko, editors), Lecture Notes in Computer Science 5010, Springer, Berlin, 2008, pp. 326-338.

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×