AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
Minimal Weak Truth Table Degrees and Computably Enumerable Turing Degrees
About this Title
Rodney G. Downey, School of Mathematics, Statistics and Operations Research, Victoria University of Wellington, Wellington, New Zealand, Keng Meng Ng, School of Physical and Mathematical Sciences, Nanyang Technological University, 21 Nanyang Link, Singapore and Reed Solomon, Department of Mathematics, University of Connecticut, Storrs, CT 06268, USA
Publication: Memoirs of the American Mathematical Society
Publication Year:
2020; Volume 265, Number 1284
ISBNs: 978-1-4704-4162-3 (print); 978-1-4704-6136-2 (online)
DOI: https://doi.org/10.1090/memo/1284
Published electronically: April 6, 2020
Keywords: Computably enumerable set,
Turing degree,
weak truth table degree,
minimal degree
MSC: Primary 03D25; Secondary 03D28, 03D30
Table of Contents
Chapters
- 1. Introduction
- 2. Informal Construction
- 3. Formal Construction
- 4. Limiting Results
Abstract
Two of the central concepts for the study of degree structures in computability theory are computably enumerable degrees and minimal degrees. For strong notions of reducibility, such as $m$-deducibility or truth table reducibility, it is possible for computably enumerable degrees to be minimal. For weaker notions of reducibility, such as weak truth table reducibility or Turing reducibility, it is not possible to combine these properties in a single degree. We consider how minimal weak truth table degrees interact with computably enumerable Turing degrees and obtain three main results. First, there are sets with minimal weak truth table degree which bound noncomputable computably enumerable sets under Turing reducibility. Second, no set with computable enumerable Turing degree can have minimal weak truth table degree. Third, no $\Delta ^0_2$ set which Turing bounds a promptly simple set can have minimal weak truth table degree.- Peter Cholak, Rod Downey, and Stephen Walk, Maximal contiguous degrees, J. Symbolic Logic 67 (2002), no. 1, 409–437. MR 1889559, DOI 10.2178/jsl/1190150052
- C. T. Chong and R. G. Downey, Degrees bounding minimal degrees, Math. Proc. Cambridge Philos. Soc. 105 (1989), no. 2, 211–222. MR 974976, DOI 10.1017/S0305004100067694
- S. B. Cooper, Minimal degrees and the jump operator, J. Symbolic Logic 38 (1973), 249–271. MR 347572, DOI 10.2307/2272061
- Barbara Flora Csima, Applications of computability theory to prime models and differential geometry, ProQuest LLC, Ann Arbor, MI, 2003. Thesis (Ph.D.)–The University of Chicago. MR 2717108
- R. Downey and N. Greenberg, A transfinite hierarchy of computably enumerable degrees, unifying classes and natural definability, in preparation.
- 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
- Rodney G. Downey and Geoffrey L. LaForte, Presentations of computably enumerable reals, Theoret. Comput. Sci. 284 (2002), no. 2, 539–555. Computability and complexity in analysis (Castle Dagstuhl, 1999). MR 1923915, DOI 10.1016/S0304-3975(01)00110-4
- R. G. Downey and J. B. Remmel, Classification of degree classes associated with r.e. subspaces, Ann. Pure Appl. Logic 42 (1989), no. 2, 105–124. MR 996503, DOI 10.1016/0168-0072(89)90051-1
- Rod Downey and Sebastiaan A. Terwijn, Computably enumerable reals and uniformly presentable ideals, MLQ Math. Log. Q. 48 (2002), no. suppl. 1, 29–40. Dagstuhl Seminar on Computability and Complexity in Analysis, 2001. MR 1948053, DOI 10.1002/1521-3870(200210)48:1+<29::AID-MALQ29>3.0.CO;2-O
- Peter A. Fejer and Richard A. Shore, A direct construction of a minimal recursively enumerable truth-table degree, Recursion theory week (Oberwolfach, 1989) Lecture Notes in Math., vol. 1432, Springer, Berlin, 1990, pp. 187–204. MR 1071518, DOI 10.1007/BFb0086118
- A. Fröhlich and J. C. Shepherdson, Effective procedures in field theory, Philos. Trans. Roy. Soc. London Ser. A 248 (1956), 407–432. MR 74349, DOI 10.1098/rsta.1956.0003
- Christine Ann Haught and Richard A. Shore, Undecidability and initial segments of the (r.e.) tt-degrees, J. Symbolic Logic 55 (1990), no. 3, 987–1006. MR 1071309, DOI 10.2307/2274468
- Christine Ann Haught and Richard A. Shore, Undecidability and initial segments of the wtt-degrees $\leq 0’$, Recursion theory week (Oberwolfach, 1989) Lecture Notes in Math., vol. 1432, Springer, Berlin, 1990, pp. 223–244. MR 1071520, DOI 10.1007/BFb0086120
- Carl G. Jockusch Jr., Simple proofs of some theorems on high degrees of unsolvability, Canadian J. Math. 29 (1977), no. 5, 1072–1080. MR 476460, DOI 10.4153/CJM-1977-105-5
- AntonĂn KuÄŤera, An alternative, priority-free, solution to Post’s problem, Mathematical foundations of computer science, 1986 (Bratislava, 1986) Lecture Notes in Comput. Sci., vol. 233, Springer, Berlin, 1986, pp. 493–500. MR 874627, DOI 10.1007/BFb0016275
- A. H. Lachlan, Distributive initial segments of the degrees of unsolvability, Z. Math. Logik Grundlagen Math. 14 (1968), 457–472. MR 237331, DOI 10.1002/malq.19680143002
- A. H. Lachlan, Initial segments of one-one degrees, Pacific J. Math. 29 (1969), 351–366. MR 260591
- A. H. Lachlan, Recursively enumerable many-one degrees, Algebra i Logika 11 (1972), 326–358, 362. MR 0309721
- A. H. Lachlan, Embedding nondistributive lattices in the recursively enumerable degrees, Conference in Mathematical Logic—London ’70 (Proc. Conf., Bedford Coll., London, 1970) Springer, Berlin, 1972, pp. 149–177. Lecture Notes in Math., Vol. 255. MR 0376318
- Richard E. Ladner and Leonard P. Sasso Jr., The weak truth table degrees of recursively enumerable sets, Ann. Math. Logic 8 (1975), no. 4, 429–448. MR 379157, DOI 10.1016/0003-4843(75)90007-8
- S. S. Marčenkov, The existence of recursively enumerable minimal truth-table degrees, Algebra i Logika 14 (1975), no. 4, 422–429 (Russian). MR 0409151
- Russell Miller, Is it harder to factor a polynomial or to find a root?, Trans. Amer. Math. Soc. 362 (2010), no. 10, 5261–5281. MR 2657679, DOI 10.1090/S0002-9947-2010-04918-9
- Alexander Nabutovsky and Shmuel Weinberger, The fractal nature of Riem/Diff. I, Geom. Dedicata 101 (2003), 1–54. MR 2017894, DOI 10.1023/A:1026358815492
- A. Nerode, General topology and partial recursive functionals, Talks from Cornell Summer Institute of Symbolic Logic, Cornell, 1957, 247–251.
- André Nies, Computability and randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. MR 2548883
- Piergiorgio Odifreddi, Strong reducibilities, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 37–86. MR 590818, DOI 10.1090/S0273-0979-1981-14863-1
- 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
- David B. Posner, A survey of non-r.e. degrees $\leq {\bf 0}^{\prime }$, Recursion theory: its generalisation and applications (Proc. Logic Colloq., Univ. Leeds, Leeds, 1979) London Math. Soc. Lecture Note Ser., vol. 45, Cambridge Univ. Press, Cambridge-New York, 1980, pp. 52–109. MR 598303
- Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284–316. MR 10514, DOI 10.1090/S0002-9904-1944-08111-1
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
- Jan Reimann and Theodore A. Slaman, Measures and their random reals, Trans. Amer. Math. Soc. 367 (2015), no. 7, 5081–5097. MR 3335411, DOI 10.1090/S0002-9947-2015-06184-4
- Gerald E. Sacks, A minimal degree less than $0’$, Bull. Amer. Math. Soc. 67 (1961), 416–419. MR 126380, DOI 10.1090/S0002-9904-1961-10652-6
- Gerald E. Sacks, The recursively enumerable degrees are dense, Ann. of Math. (2) 80 (1964), 300–312. MR 166089, DOI 10.2307/1970393
- Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921
- Robert I. Soare, Computability theory and differential geometry, Bull. Symbolic Logic 10 (2004), no. 4, 457–486. MR 2136634, DOI 10.2178/bsl/1102083758
- Clifford Spector, On degrees of recursive unsolvability, Ann. of Math. (2) 64 (1956), 581–592. MR 82457, DOI 10.2307/1969604
- Rebecca M. Steiner, Computable fields and the bounded Turing reduction, Ann. Pure Appl. Logic 163 (2012), no. 6, 730–742. MR 2889557, DOI 10.1016/j.apal.2011.11.007
- C. E. M. Yates, Initial segments of the degrees of unsolvability. II. Minimal degrees, J. Symbolic Logic 35 (1970), 243–266. MR 274288, DOI 10.2307/2270517