A completely mitotic nonrecursive r.e. degree
HTML articles powered by AMS MathViewer
- by Richard E. Ladner PDF
- Trans. Amer. Math. Soc. 184 (1973), 479-507 Request permission
Abstract:
A nonrecursive r.e. degree d is constructed that has the property that every r.e. set of degree d is mitotic. The degree d has several other interesting properties including the property that any two r.e. sets of degree d are weak truth table equivalent.References
- Carl G. Jockusch Jr., Degrees in which the recursive sets are uniformly recursive, Canadian J. Math. 24 (1972), 1092–1099. MR 321716, DOI 10.4153/CJM-1972-113-9
- Richard E. Ladner, Mitotic recursively enumerable sets, J. Symbolic Logic 38 (1973), 199–211. MR 342381, DOI 10.2307/2272056
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
- Leonard P. Sasso Jr., Deficiency sets and bounded information reducibilities, Trans. Amer. Math. Soc. 200 (1974), 267–290. MR 469729, DOI 10.1090/S0002-9947-1974-0469729-2
- C. E. M. Yates, Three theorems on the degrees of recursively enumerable sets, Duke Math. J. 32 (1965), 461–468. MR 180486
- C. E. M. Yates, On the degrees of index sets. II, Trans. Amer. Math. Soc. 135 (1969), 249–266. MR 241295, DOI 10.1090/S0002-9947-1969-0241295-4
Additional Information
- © Copyright 1973 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 184 (1973), 479-507
- MSC: Primary 02F25
- DOI: https://doi.org/10.1090/S0002-9947-1973-0398805-7
- MathSciNet review: 0398805