A completely mitotic nonrecursive r.e. degree

Ladner, Richard E.

doi:10.1090/S0002-9947-1973-0398805-7

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