×

zbMATH — the first resource for mathematics

Mass problems associated with effectively closed sets. (English) Zbl 1246.03064
In the paper recent investigations into the lattice of Muchnik degrees of nonempty effectively closed sets in Euclidean space \({\mathcal E}_{w}\) are summerized. In particular it is shown that \({\mathcal E}_{w}\) provides an elegant and useful framework for the classification of certain foundationally interesting problems which are algorithmically unsolvable. Some specific degrees in \({\mathcal E}_{w}\) which are associated with such problems are exhibited. Additionally, some structural results concerning the lattice \({\mathcal E}_{w}\) are presented. One of them gives an answer to a question which arises naturally from the Kolmogorov non-rigorous 1932 interpretation of intuitionism as a calculus of problems. It is also shown how \({\mathcal E}_{w}\) can be applied in symbolic dynamics toward the classification of tiling problems and \({\mathbb Z}^{d}\)-subshifts of finite type.

MSC:
03D30 Other degrees and reducibilities in computability and recursion theory
03D25 Recursively (computably) enumerable sets and degrees
03D28 Other Turing degree structures
03D32 Algorithmic randomness and dimension
03D55 Hierarchies of computability and definability
37B10 Symbolic dynamics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] S. Aanderaa and D. E. Cohen, Modular machines I, II, in [wp2?], Stud. Logic Found. Math. 95 (1980), 1-18, 19-28. · Zbl 0445.20016 · doi:10.1016/S0049-237X(08)71327-2
[2] S. I. Adian, W. W. Boone and G. Higman (eds.), Word problems II: The Oxford Book, Stud. Logic Found. Math. 95, North-Holland Publishing Co., Amsterdam, New York, 1980.
[3] K. Ambos-Spies, B. Kjos-Hanssen, S. Lempp and T. A. Slaman, Comparing DNR and WWKL, J. Symbolic Logic 69 (2004), 1089-1104. · Zbl 1076.03039 · doi:10.2178/jsl/1102022212
[4] J. Barwise, H. J. Keisler and K. Kunen (eds.), The Kleene Symposium, Stud. Logic Found. Math. 101, North-Holland, Publishing Co., Amsterdam-New York, 1980.
[5] R. Berger, The undecidability of the domino problem, Mem. Amer. Math. Soc. 66, American Mathematical Society, 1966. · Zbl 0199.30802
[6] S. Binns, A splitting theorem for the Medvedev and Muchnik lattices, MLQ Math. Log. Q. 49 (2003), 327-335. · Zbl 1022.03021 · doi:10.1002/malq.200310034
[7] S. Binns, Small \(\Pi^0_1\) classes, Arch. Math. Logic 45 (2006), 393-410. · Zbl 1147.03024 · doi:10.1007/s00153-005-0319-6
[8] S. Binns, Hyperimmunity in \(2^{\boldsymbol{N}}\), Notre Dame J. Formal Logic 48 (2007), 293-316. · Zbl 1139.03029 · doi:10.1305/ndjfl/1179323269
[9] S. Binns, \(\Pi^0_1\) classes with complex elements, J. Symbolic Logic 73 (2008), 1341-1353. · Zbl 1155.03032 · doi:10.2178/jsl/1230396923
[10] S. Binns, B. Kjos-Hanssen, M. Lerman and D. R. Solomon, On a question of Dobrinen and Simpson concerning almost everywhere domination, J. Symbolic Logic 71 (2006), 119-136. · Zbl 1103.03014 · doi:10.2178/jsl/1140641165
[11] S. Binns and S. G. Simpson, Embeddings into the Medvedev and Muchnik lattices of \(\Pi^0_1\) classes, Arch. Math. Logic 43 (2004), 399-414. · Zbl 1058.03041 · doi:10.1007/s00153-003-0195-x
[12] G. Birkhoff, Lattice theory, American Mathematical Society, 1940. · Zbl 0063.00402
[13] G. Birkhoff, Lattice theory, revised edition, Amer. Math. Soc. Colloq. Pub. 25, American Mathematical Society, New York, 1948. · Zbl 0033.10103
[14] G. Birkhoff, Lattice theory, third edition, Amer. Math. Soc. Colloq. Pub. 25, American Mathematical Society, Providence, R.I., 1967. · Zbl 0153.02501
[15] M. Boyle, Open problems in symbolic dynamics, Contemp. Math. 469, 69-118 in [cm-469?], Amer. Math. Soc., Providence, RI, 2008. · Zbl 1158.37007 · doi:10.1090/conm/469/09161
[16] D. K. Brown, M. Giusto and S. G. Simpson, Vitali’s theorem and WWKL, Arch. Math. Logic 41 (2002), 191-206. · Zbl 1030.03044 · doi:10.1007/s001530100100
[17] K. Burns, D. Dolgopyat and Y. Pesin (eds.), Geometric and probabilistic structures in dynamics, Contemp. Math. 469, American Mathematical Society, Providence, RI, 2008.
[18] J.-Y. Cai, S. B. Cooper and A. Li (eds.), Theory and applications of models of computation, Lecture Notes in Comput. Sci. 3959, Springer-Verlag, Berlin, 2006.
[19] P. Cholak, R. Coles, R. Downey and E. Herrmann, Automorphisms of the lattice of \(\Pi^0_1\) classes; perfect thin classes and ANC degrees, Trans. Amer. Math. Soc. 353 (2001), 4899-4924. · Zbl 0978.03033 · doi:10.1090/S0002-9947-01-02821-5
[20] P. Cholak, N. Greenberg and J. S. Miller, Uniform almost everywhere domination, J. Symbolic Logic 71 (2006), 1057-1072. · Zbl 1109.03034 · doi:10.2178/jsl/1154698592
[21] C.-T. Chong, Q. Feng, T. A. Slaman, W. H. Woodin and Y. Yang (eds.), Computational Prospects of Infinity: Proceedings of the Logic Workshop at the Institute for Mathematical Sciences, June 20–August 15, 2005, Part II: Presented Talks, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, 15, World Scientific Publishing Co. Pre. Ltd., Hackensack, NJ, 2008.
[22] J. A. Cole and S. G. Simpson, Mass problems and hyperarithmeticity, J. Math. Logic 7 (2008), 125-143. · Zbl 1150.03013 · doi:10.1142/S0219061307000652
[23] B. A. Davey and H. A. Priestley, Introduction to lattices and order, Cambridge University Press, 1990. · Zbl 0701.06001
[24] M. Davis, Hilbert’s tenth problem is unsolvable, Amer. Math. Monthly 80 (1973), 233-269. · Zbl 0277.02008 · doi:10.2307/2318447
[25] A. R. Day and J. S. Miller, Randomness for non-computable measures, to appear in Trans. Amer. Math. Soc. · Zbl 1307.03026 · doi:10.1090/S0002-9947-2013-05682-6
[26] J. C. E. Dekker (ed.), Recursive function theory, Proc. Symp. Pure Math., American Mathematical Society, Providence, R.I., 1962. · Zbl 0192.05301
[27] N. L. Dobrinen and S. G. Simpson, Almost everywhere domination, J. Symbolic Logic 69 (2004), 914-922. · Zbl 1075.03021 · doi:10.2178/jsl/1096901775
[28] R. G. Downey and D. Hirschfeldt, Algorithmic randomness and complexity, Theory Appl. Comput., Springer-Verlag, New York, 2010. · Zbl 1221.68005
[29] B. Durand and W. Thomas (eds.), STACS 2006: Proceedings of the Twenty-Third Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Lecture Notes in Computer Science 3884, Springer-Verlag, Berlin, 2006.
[30] B. Durand, A. Romashchenko and A. Shen, Fixed-point tile sets and their applications, 2010, arXiv: · Zbl 1244.05049 · doi:10.1016/j.jcss.2011.11.001 · arxiv.org
[31] H.-D. Ebbinghaus, G. H. Müller and G. E. Sacks (eds.), Recursion theory week, Lecture Notes in Math. 1141, Springer-Verlag, 1985. · Zbl 0566.00001
[32] K. Falconer, Fractal geometry, 2nd edition, John Wiley & Sons, Inc., Hoboken, NJ, 2003. · Zbl 1060.28005
[33] S. Feferman, C. Parsons and S. G. Simpson (eds.), Kurt Gödel: essays for his centennial, Lect. Notes in Log. 33, Assoc. Symbol. Logic, Cambridge University Press, Cambridge, 2010. · Zbl 1196.03006
[34] J.-E. Fenstad, I. T. Frolov and R. Hilpinen (eds.), Logic, methodology and philosophy of science VIII, Stud. Logic Found. Math. 126, North-Holland, Amsterdam, 1989.
[35] FOM e-mail list, http://www.cs.nyu.edu/mailman/listinfo/fom/, September 1997 to the present.
[36] R. O. Gandy, G. Kreisel and W. W. Tait, Set existence, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 8 (1960), 577-582. · Zbl 0207.30102
[37] K. Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I, Monatsh. Math. Phys. 38 (1931), 173-198. · Zbl 0002.00101 · doi:10.1007/BF01700692
[38] O. Goldreich, Computational complexity: a conceptual perspective, Cambridge University Press, Cambridge, 2008. · Zbl 1154.68056
[39] D. Hilbert, Mathematical problems, Bull. Amer. Math. Soc. 8 (1902), 437-479. · JFM 33.0976.07 · doi:10.1090/S0002-9904-1902-00923-3
[40] P. G. Hinman, Recursion-theoretic hierarchies, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, New York, 1978. · Zbl 0371.02017
[41] J. M. Hitchcock, J. H. Lutz and E. Mayordomo, The fractal geometry of complexity classes, SIGACT News 36 (2005), 24-38.
[42] M. Hochman and T. Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type, Ann. Math. 171 (2010), 2011-2038. · Zbl 1192.37022 · doi:10.4007/annals.2010.171.2011 · annals.princeton.edu
[43] P. Hudelson, Mass problems and initial segment complexity, 2010, in preparation. · Zbl 1337.03061
[44] C. G. Jockusch, Jr., Degrees of functions with no fixed points, in [lmps8?] (1989), 191-201. · Zbl 0694.03027
[45] C. G. Jockusch, Jr. and R. A. Shore, Pseudo-jump operators I: the r.e. case, Trans. Amer. Math. Soc. 275 (1983), 599-609. · Zbl 0514.03028 · doi:10.2307/1999041
[46] C. G. Jockusch, Jr. and R. A. Shore, Pseudo-jump operators II: transfinite iterations, hierarchies, and minimal covers, J. Symbolic Logic 49 (1984), 1205-1236. · Zbl 0574.03026 · doi:10.2307/2274273
[47] C. G. Jockusch, Jr. and S. G. Simpson, A degree theoretic definition of the ramified analytical hierarchy, Ann. Math. Logic 10 (1976), 1-32. · Zbl 0333.02039 · doi:10.1016/0003-4843(76)90023-1
[48] C. G. Jockusch, Jr. and R. I. Soare, Degrees of members of \(\Pi^0_1\) classes, Pacific J. Math. 40 (1972), 605-616. · Zbl 0209.02201 · doi:10.2140/pjm.1972.40.605
[49] C. G. Jockusch, Jr. and R. I. Soare, \(\Pi^0_1\) classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 35-56. · Zbl 0262.02041 · doi:10.2307/1996261
[50] A. S. Kechris, Classical descriptive set theory, Grad. Texts in Math. 156, Springer-Verlag, New York, 1995. · Zbl 0819.04002
[51] T. Kent and A. E. M. Lewis, On the degree spectrum of a \(\Pi^0_1\) class, Trans. Amer. Math. Soc. 362 (2010), 5283-5319. · Zbl 1230.03074 · doi:10.1090/S0002-9947-10-05037-3
[52] B. Kjos-Hanssen, Low-for-random reals and positive-measure domination, Proc. Amer. Math. Soc. 135 (2007), 3703-3709. · Zbl 1128.03031 · doi:10.1090/S0002-9939-07-08648-0
[53] B. Kjos-Hanssen, W. Merkle and F. Stephan, Kolmogorov complexity and the recursion theorem, 149-161 in [stacs06?], Lecture Notes in Comput. Sci. 3884, Springer, Berlin, 2006. · Zbl 1137.03026 · doi:10.1007/11672142_11
[54] B. Kjos-Hanssen, J. S. Miller and D. R. Solomon, Lowness notions, measure and domination, to appear in Proc. London Math. Soc. · Zbl 1262.03068 · doi:10.1112/jlms/jdr072
[55] B. Kjos-Hanssen and S. G. Simpson, Mass problems and Kolmogorov complexity, October 2006, in preparation.
[56] S. C. Kleene and E. L. Post, The upper semi-lattice of degrees of recursive unsolvability, Ann. Math. 59 (1954), 379-407. · Zbl 0057.24703 · doi:10.2307/1969708
[57] A. Kolmogoroff, Zur Deutung der intuitionistischen Logik, Math. Z. 35 (1932), 58-65. · Zbl 0004.00201 · doi:10.1007/BF01186549 · eudml:168345
[58] A. N. Kolmogorov, On the interpretation of intuitionistic logic, in [k-sel-1?] (1991), 151-158, 451-466. (Translation of [k-iil?] with commentary and additional references.)
[59] M. Kumabe and A. E. M. Lewis, A fixed-point-free minimal degree, J. London Math. Soc. (2) 80 (2009), 785-797. · Zbl 1183.03030 · doi:10.1112/jlms/jdp049
[60] A. Kučera, Measure, \(\Pi^0_1\) classes and complete extensions of PA, Recursion theory week (Oberwolfach, 1984), 245-259 in [rtw85?], Lecture Notes in Math. 1141, Springer, Berlin, 1985. · Zbl 0622.03031 · doi:10.1007/BFb0076224
[61] M. Lerman, A framework for priority arguments, Lecture Notes in Logic 34, Association for Symbolic Logic, Cambridge University Press, Cambridge, 2010. · Zbl 1203.03054
[62] M. Li and P. Vitányi, An introduction to Kolmogorov complexity and its applications, 2nd edition, Grad. Texts in Comput. Sci., Springer-Verlag, New York, 1997.
[63] D. Lind and B. Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995. · Zbl 1106.37301 · doi:10.1017/CBO9780511626302
[64] S. MacLane and I. Moerdijk, Sheaves in geometry and logic: a first introduction to topos theory, Universitext, Springer-Verlag, New York, 1992. · Zbl 0822.18001
[65] R. Mansfield and G. Weitkamp, Recursive aspects of descriptive set theory, Oxford Logic Guides 11, Oxford University Press, New York, 1985. · Zbl 0655.03032
[66] P. Martin-Löf, The definition of random sequences, Information and Control 9 (1966), 602-619. · Zbl 0244.62008 · doi:10.1016/S0019-9958(66)80018-9
[67] Y. T. Medvedev, Degrees of difficulty of mass problems, Dokl. Akad. Nauk SSSR (N.S.) 104 (1955), 501-504.
[68] J. S. Miller, Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension, Adv. Math. 226 (2011), 373-384. · Zbl 1214.03030 · doi:10.1016/j.aim.2010.06.024
[69] Y. N. Moschovakis, Descriptive set theory, Stud. Logic Found. Math. 100, North-Holland Publishing Co., Amsterdam, New York, 1980. · Zbl 0433.03025
[70] S. Mozes, Tilings, substitution systems, and the dynamical systems generated by them, J. Analyse Math. 53 (1989), 139-186. · Zbl 0745.52013 · doi:10.1007/BF02793412
[71] A. A. Muchnik, On strong and weak reducibilities of algorithmic problems, Sibirskii Matematicheskii Zhurnal 4 (1963), 1328-1341.
[72] D. Myers, Nonrecursive tilings of the plane, II, J. Symbolic Logic 39 (1974), 286-294. · Zbl 0299.02055 · doi:10.2307/2272641
[73] A. Nabutovsky, Einstein structures: existence versus uniqueness, Geom. Funct. Anal. 5 (1995), 76-91. · Zbl 0842.53032 · doi:10.1007/BF01928216 · eudml:58184
[74] A. Nabutovsky and S. Weinberger, Betti numbers of finitely presented groups and very rapidly growing functions, Topology 46 (2007), 211-233. · Zbl 1139.20030 · doi:10.1016/j.top.2007.02.002
[75] A. Nies, Lowness properties and randomness, Adv. Math. 197 (2005), 274-305. · Zbl 1141.03017 · doi:10.1016/j.aim.2004.10.006
[76] A. Nies, Computability and randomness, Oxford Logic Guides 51, Oxford University Press, Oxford, 2009.
[77] A. Nies, R. A. Shore and T. A. Slaman, Interpretability and definability in the recursively enumerable degrees, Proc. London Math. Soc. (3) 77 (1998), 241-291. · Zbl 0904.03028 · doi:10.1112/S002461159800046X
[78] D. B. Posner and R. W. Robinson, Degrees joining to \(0'\), J. Symbolic Logic 46 (1981), 714-722. · Zbl 0517.03014 · doi:10.2307/2273221
[79] M. B. Pour-El and S. Kripke, Deduction-preserving “recursive isomorphisms” between theories, Fund. Math. 61 (1967), 141-163. · Zbl 0174.02003 · eudml:213983
[80] M. O. Rabin, Recursive unsolvability of group theoretic problems, Ann. Math. 67 (1958), 172-194. · Zbl 0079.24802 · doi:10.2307/1969933
[81] D. Richardson, Some undecidable problems involving elementary functions of a real variable, J. Symbolic Logic 33 (1968), 514-520. · Zbl 0175.27404 · doi:10.2307/2271358
[82] R. M. Robinson, Undecidability and nonperiodicity of tilings of the plane, Invent. Math. 12 (1971), 177-209. · Zbl 0197.46801 · doi:10.1007/BF01418780 · eudml:142073
[83] H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. · Zbl 0183.01401
[84] G. E. Sacks, The recursively enumerable degrees are dense, Ann. Math. 80 (1964), 300-312. · Zbl 0135.00702 · doi:10.2307/1970393
[85] G. E. Sacks, Degrees of unsolvability, 2nd edition, Ann. Math. Studies 55, Princeton University Press, Princeton, 1966.
[86] G. E. Sacks, Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. · Zbl 0716.03043
[87] K. Schütte, Proof theory, Grundlehren der Mathematischen Wissenschaften 225, Springer-Verlag, Berlin-New York, 1977.
[88] D. S. Scott, Algebras of sets binumerable in complete extensions of arithmetic, Proc. Sympos. Pure Math. 5, 117-121 in [rec-fcn-thy?], American Mathematical Society, Providence, R.I., 1962. · Zbl 0199.02601
[89] D. S. Scott and S. Tennenbaum, On the degrees of complete extensions of arithmetic (abstract), Notices Amer. Math. Soc. 7 (1960), 242-243.
[90] R. A. Shore and T. A. Slaman, Defining the Turing jump, Math. Res. Lett. 6 (1999), 711-722. · Zbl 0958.03029 · doi:10.4310/MRL.1999.v6.n6.a10
[91] S. G. Simpson (ed.), Reverse mathematics 2001, Lecture Notes in Logic 21, Association for Symbolic Logic, La Jolla, CA; A. K. Peters, Ltd., Wellesley, MA, 2005. · Zbl 0578.03005
[92] S. G. Simpson, The hierarchy based on the jump operator, in [kleene-symp?] (1980), 203-212. · Zbl 0498.03039
[93] S. G. Simpson, FOM: natural r.e. degrees; Pi01 classes, FOM e-mail list [fom?], 13 August, 1999.
[94] S. G. Simpson, FOM: priority arguments; Kleene-r.e. degrees; Pi01 classes, FOM e-mail list [fom?], 16 August, 1999.
[95] S. G. Simpson, Subsystems of second order arithmetic, Perspect. in Math. Logic, Springer-Verlag, Berlin, 1999; Second Edition, Perspect. Logic, Association for Symbolic Logic, Cambridge University Press, Cambridge, 2009. · Zbl 0909.03048
[96] S. G. Simpson, Mass problems and randomness, Bull. Symbolic Logic 11 (2005), 1-27. · Zbl 1090.03015 · doi:10.2178/bsl/1107959497
[97] S. G. Simpson, \(\Pi^0_1\) sets and models of \(\mathsf{WKL}_0\), Reverse mathematics 2001, 352-378 in [rm2001?], Lect. Notes Log. 21, Assoc. Symbol. Logic, La Jolla, CA, 2005. · Zbl 1106.03051
[98] S. G. Simpson, Almost everywhere domination and superhighness, MLQ Math. Log. Q. 53 (2007), 462-482. · Zbl 1123.03040 · doi:10.1002/malq.200710012
[99] S. G. Simpson, An extension of the recursively enumerable Turing degrees, J. London Math. Soc. 75 (2007), 287-297. · Zbl 1119.03037 · doi:10.1112/jlms/jdl015
[100] S. G. Simpson, Mass problems and almost everywhere domination, MLQ Math. Log. Q. 53 (2007), 483-492. · Zbl 1123.03041 · doi:10.1002/malq.200710013
[101] S. G. Simpson, Mass problems and intuitionism, Notre Dame J. Form. Log. 49 (2008), 127-136. · Zbl 1141.03018 · doi:10.1215/00294527-2008-002
[102] S. G. Simpson, Some fundamental issues concerning degrees of unsolvability, in [cpoi?] (2008), 313-332. · Zbl 1157.03020 · doi:10.1142/9789812796554_0017
[103] S. G. Simpson, Mass problems and measure-theoretic regularity, Bull. Symbolic Logic 15 (2009), 385-409. · Zbl 1191.03007 · doi:10.2178/bsl/1255526079
[104] S. G. Simpson, The Gödel hierarchy and reverse mathematics, Kurt Gödel: essays for his centennial, 109-127 in [godel-fps?], Lect. Notes Log. 33, Assoc. Symbol. Logic, La Jolla, CA, 2010. · Zbl 1223.03006
[105] S. G. Simpson, Medvedev degrees of 2-dimensional subshifts of finite type, to appear in Ergodic Theory and Dynamical Systems. · Zbl 1351.37053
[106] S. G. Simpson, Symbolic dynamics: entropy \(=\) dimension \(=\) complexity, 2010, in preparation.
[107] R. I. Soare, Recursively enumerable sets and degrees, Perspect. Math. Logic, Springer-Verlag, Berlin, 1987. · Zbl 0667.03030
[108] A. Sorbi and S. A. Terwijn, Intuitionistic logic and Muchnik degrees, preprint, 2010, arXiv: · Zbl 1252.03101 · doi:10.1007/s00012-012-0176-1 · arxiv.org
[109] J. R. Steel, Descending sequences of degrees, J. Symbolic Logic 40 (1975), 59-61. · Zbl 0349.02036 · doi:10.2307/2272271
[110] A. Stukachev, On mass problems of presentability, Theory and applications of models of computation, 772-782 in [lncs3959?], Lecture Notes in Comput. Sci. 3959, Springer, Berlin, 2006. · Zbl 1178.03045 · doi:10.1007/11750321
[111] G. Takeuti, Proof theory, 2nd edition, Stud. Logic Found. Math. 81. North-Holland Publishing Co., Amsterdam, 1987. · Zbl 0609.03019
[112] A. Tarski, A. Mostowski and R. M. Robinson, Undecidable theories, Stud. Logic Found. Math., North-Holland Publishing Co., Amsterdam, 1953. · Zbl 0053.00401
[113] V. M. Tikhomirov (ed.), Selected works of A. N. Kolmogorov, Volume I, mathematics and mechanics, Math. Appl. (Soviet Series) 25, Kluwer Academic Publishers Group, Dordrecht, 1991.
[114] A. S. Troelstra and D. van Dalen, Constructivism in mathematics, an Introduction, Vol. I, II, Stud. Log. Found. Math. 121, 123, North-Holland Publishing Co., Amsterdam, 1988. · Zbl 0661.03047
[115] A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc. (2) 42 (1936), 230-265. · Zbl 0016.09701 · doi:10.1112/plms/s2-42.1.230
[116] S. S. Wainer, A classification of the ordinal recursive functions, Arch. Math. Logik und Grundlagenforsch. 13 (1970), 136-153. · Zbl 0228.02027 · doi:10.1007/BF01973619 · eudml:137841
[117] H. Wang, Proving theorems by pattern recognition, II, Bell System Tech. J. 40 (1961), 1-42.
[118] R. Weber, Invariance in \(\mathcal{E}^*\) and \(\mathcal{E}_\Pi\), Trans. Amer. Math. Soc. 358 (2006), 3023-3059. · Zbl 1093.03026 · doi:10.1090/S0002-9947-06-03984-5
[119] X. Yu and S. G. Simpson, Measure theory and weak König’s lemma, Arch. Math. Logic 30 (1990), 171-180. · Zbl 0718.03043 · doi:10.1007/BF01621469
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.