Working with strong reducibilities above totally 𝜔-c.e. and array computable degrees

Barmpalias, George; Downey, Rod; Greenberg, Noam

doi:10.1090/S0002-9947-09-04910-1

Working with strong reducibilities above totally $\omega$-c.e. and array computable degrees
HTML articles powered by AMS MathViewer

by George Barmpalias, Rod Downey and Noam Greenberg PDF

Trans. Amer. Math. Soc. 362 (2010), 777-813 Request permission

Abstract:

We investigate the connections between the complexity of a c.e. set, as calibrated by its strength as an oracle for Turing computations of functions in the Ershov hierarchy, and how strong reducibilities allow us to compute such sets. For example, we prove that a c.e. degree is totally $\omega$-c.e. iff every set in it is weak truth-table reducible to a hypersimple, or ranked, set. We also show that a c.e. degree is array computable iff every left-c.e. real of that degree is reducible in a computable Lipschitz way to a random left-c.e. real (an $\Omega$-number).

References

Bahareh Afshari, George Barmpalias, S. Barry Cooper, and Frank Stephan, Post’s programme for the Ershov hierarchy, J. Logic Comput. 17 (2007), no. 6, 1025–1040. MR 2376073, DOI 10.1093/logcom/exm032
George Barmpalias, Computability and applications to analysis, Ph.D. thesis, University of Leeds, U.K., 2004.
George Barmpalias, Hypersimplicity and semicomputability in the weak truth table degrees, Arch. Math. Logic 44 (2005), no. 8, 1045–1065. MR 2193189, DOI 10.1007/s00153-005-0288-9
Andrew E. M. Lewis and George Barmpalias, Random reals and Lipschitz continuity, Math. Structures Comput. Sci. 16 (2006), no. 5, 737–749. MR 2268340, DOI 10.1017/S0960129506005445
George Barmpalias and Andrew E. M. Lewis, The ibT degrees of computably enumerable sets are not dense, Ann. Pure Appl. Logic 141 (2006), no. 1-2, 51–60. MR 2229929, DOI 10.1016/j.apal.2005.10.001
Andrew E. M. Lewis and George Barmpalias, Randomness and the linear degrees of computability, Ann. Pure Appl. Logic 145 (2007), no. 3, 252–257. MR 2286414, DOI 10.1016/j.apal.2006.08.001
George Barmpalias and Andrew E. M. Lewis, A c.e. real that cannot be sw-computed by any $\Omega$ number, Notre Dame J. Formal Logic 47 (2006), no. 2, 197–209. MR 2240619, DOI 10.1305/ndjfl/1153858646
John Chisholm, Jennifer Chubb, Valentina S. Harizanov, Denis R. Hirschfeldt, Carl G. Jockusch Jr., Timothy McNicholl, and Sarah Pingrey, $\Pi ^0_1$ classes and strong degree spectra of relations, J. Symbolic Logic 72 (2007), no. 3, 1003–1018. MR 2354911, DOI 10.2178/jsl/1191333852
Chris J. Conidis, Classifying model-theoretic properties, J. Symbolic Logic 73 (2008), no. 3, 885–905. MR 2444274, DOI 10.2178/jsl/1230396753
Barbara F. Csima and Robert I. Soare, Computability results used in differential geometry, J. Symbolic Logic 71 (2006), no. 4, 1394–1410. MR 2275866, DOI 10.2178/jsl/1164060462
David Doty, Every sequence is decompressible from a random one. in Arnold Beckmann et al. (eds.), Logical approaches to computational barriers, Proceedings of the second conference on computability in Europe, Lecture Notes in Computer Science 3988, Springer-Verlag, 2006, 153–162.
Rod Downey and Noam Greenberg, Totally $<\omega ^\omega$-computably enumerable degrees and embeddings of the 1-3-1 lattice, in preparation.
Rod Downey and Noam Greenberg, Totally $<\omega ^\omega$ computably enumerable and $m$-topped degrees, Theory and applications of models of computation, Lecture Notes in Comput. Sci., vol. 3959, Springer, Berlin, 2006, pp. 46–60. MR 2277228, DOI 10.1007/11750321_{3}
Rod Downey and Noam Greenberg, Turing degrees of reals of positive effective packing dimension, Inform. Process. Lett. 108 (2008), no. 5, 298–303. MR 2456604, DOI 10.1016/j.ipl.2008.05.028
Rod Downey, Noam Greenberg, and Rebecca Weber, Totally $\omega$-computably enumerable degrees and bounding critical triples, J. Math. Log. 7 (2007), no. 2, 145–171. MR 2423948, DOI 10.1142/S0219061307000640
Rod Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Springer, to appear.
Rod G. Downey, Denis R. Hirschfeldt, and Geoff LaForte, Randomness and reducibility, Mathematical foundations of computer science, 2001 (Mariánské Láznĕ), Lecture Notes in Comput. Sci., vol. 2136, Springer, Berlin, 2001, pp. 316–327. MR 1907022, DOI 10.1007/3-540-44683-4_{2}8
Rod G. Downey, Denis R. Hirschfeldt, and Geoff LaForte, Randomness and reducibility, J. Comput. System Sci. 68 (2004), no. 1, 96–114. MR 2030512, DOI 10.1016/j.jcss.2003.07.004
Rod Downey, Carl Jockusch, and Michael Stob, Array nonrecursive sets and multiple permitting arguments, Recursion theory week (Oberwolfach, 1989) Lecture Notes in Math., vol. 1432, Springer, Berlin, 1990, pp. 141–173. MR 1071516, DOI 10.1007/BFb0086116
Denis R. Hirschfeldt, Richard A. Shore, and Theodore A. Slaman, The atomic model theorem, Preprint.
Rod Downey, Carl G. Jockusch, and Michael Stob, Array nonrecursive degrees and genericity, Computability, enumerability, unsolvability, London Math. Soc. Lecture Note Ser., vol. 224, Cambridge Univ. Press, Cambridge, 1996, pp. 93–104. MR 1395876, DOI 10.1017/CBO9780511629167.005
Stephen Fenner and Marcus Schaefer, Bounded immunity and btt-reductions, MLQ Math. Log. Q. 45 (1999), no. 1, 3–21. MR 1669934, DOI 10.1002/malq.19990450102
Péter Gács, Every sequence is reducible to a random one, Inform. and Control 70 (1986), no. 2-3, 186–192. MR 859105, DOI 10.1016/S0019-9958(86)80004-3
Shamil Ishmukhametov, Weak recursive degrees and a problem of Spector, Recursion theory and complexity (Kazan, 1997) De Gruyter Ser. Log. Appl., vol. 2, de Gruyter, Berlin, 1999, pp. 81–87. MR 1724934
Bjørn Kjos-Hanssen, Wolfgang Merkle, and Frank Stephan, Kolmogorov complexity and the recursion theorem, STACS 2006, Lecture Notes in Comput. Sci., vol. 3884, Springer, Berlin, 2006, pp. 149–161. MR 2249365, DOI 10.1007/11672142_{1}1
Antonín Kučera, Measure, $\Pi ^0_1$-classes and complete extensions of $\textrm {PA}$, Recursion theory week (Oberwolfach, 1984) Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245–259. MR 820784, DOI 10.1007/BFb0076224
Antonín Kučera, On the use of diagonally nonrecursive functions, Logic Colloquium ’87 (Granada, 1987) Stud. Logic Found. Math., vol. 129, North-Holland, Amsterdam, 1989, pp. 219–239. MR 1015310, DOI 10.1016/S0049-237X(08)70130-7
Antonín Kučera and Theodore A. Slaman, Randomness and recursive enumerability, SIAM J. Comput. 31 (2001), no. 1, 199–211. MR 1857396, DOI 10.1137/S0097539799357441
Martin Kummer, Kolmogorov complexity and instance complexity of recursively enumerable sets, SIAM J. Comput. 25 (1996), no. 6, 1123–1143. MR 1417892, DOI 10.1137/S0097539794268789
Ming Li and Paul Vitányi, An introduction to Kolmogorov complexity and its applications, 2nd ed., Graduate Texts in Computer Science, Springer-Verlag, New York, 1997. MR 1438307, DOI 10.1007/978-1-4757-2606-0
Wolfgang Merkle and Nenad Mihailović, On the construction of effectively random sets, J. Symbolic Logic 69 (2004), no. 3, 862–878. MR 2078927, DOI 10.2178/jsl/1096901772
André Nies. Computability and Randomness. Oxford University Press, in preparation, 2009.
Keng Meng Ng, Frank Stephan and Guohua Wu, Degrees of weakly computable reals, Proceedings of “Second Conference on Computability in Europe”, CiE 2006, Swansea (2006), 413–422.
Piergiorgio Odifreddi, Classical recursion theory, Studies in Logic and the Foundations of Mathematics, vol. 125, North-Holland Publishing Co., Amsterdam, 1989. The theory of functions and sets of natural numbers; With a foreword by G. E. Sacks. MR 982269
Liang Yu and Decheng Ding, There is no $SW$-complete c.e. real, J. Symbolic Logic 69 (2004), no. 4, 1163–1170. MR 2135660, DOI 10.2178/jsl/1102022216