On Initial Segments of Turing Degrees Containing Simple T-Mitotic but not wtt-Mitotic Sets
DOI:
https://doi.org/10.51408/1963-0039Keywords:
Mitotic set, T-reducibility, wtt-reducibility, Simple set, Contiguous degreeAbstract
We consider the properties of computably enumerable (c.e.) Turing degrees containing sets, which possess the property of a T-mitotic splitting but don't have a wtt-mitotic splitting. It is proved that for any noncomputable c.e. degree b there exists a degree a, such that a · b and a contains a simple T- itotic set, which is not wtt-mitotic.
References
R. I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, 1987.
H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill Book Company, 1967.
R. G. Downey and M. Stob, Splitting Theorems In Recursion Theory", Ann. Pure Appl. Logic, vol. 65, pp. 1-106, 1993.
A. H. Lachlan,The Priority Method. I, Zeitschrift fr mathematische Logik und Grundlagen der Mathematik, vol.1 3, pp. 1-10, 1967.
R.Ladner A complete mitotic recursively enumerable degree", Trans. Amer. Math. Soc., 184, pp. 497-507, 1973.
R. Ladner and L. Sasso, The weak truth-table degrees of recursively enumerable sets", Arch. Math. Logik Grundlang Grundlagen der Mathematik, vol. 8, pp. 429-448, 1975.
M. Ingrassia, P-generecity for recursive enumerable degrees, PhD. Thesis, University of Illinois, 1981.
R. G. Downey and T. A. S laman, Completely Mitotic R. E. Degrees", Ann. Pure Appl. Logic, vol. 41, pp. 119-152, 1989.
E. J. Griffths, Completely Mitotic Turing Degrees, Jump Classes and E numeration Degrees, PhD. Thesis, University of Wisconsin-Madison, 1998.
R. Ladner, Mitotic Recursively Enumerable Sets", The Journal of Symbolic Logic, vol. 38, no.2, pp. 199-211 , 1973.
B. A. Trakhtenbrot, On autoreducibility" (in Russian), Dokl. Akad. Nauk SSSR, vol. 192, pp. 1224-1227, 1970.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
