The homogeneity conjecture
- 1 September 1979
- journal article
- Published by Proceedings of the National Academy of Sciences in Proceedings of the National Academy of Sciences
- Vol. 76 (9) , 4218-4219
- https://doi.org/10.1073/pnas.76.9.4218
Abstract
We show that, for any function f in which Kleene's O is computable, the ordering of Turning degrees (i.e., degrees of difficulty of computation of functions) is not isomorphic to the ordering of degrees of functions from which f is computable. This refutes a well-known conjecture of H. Rogers, Jr., and others.Keywords
This publication has 0 references indexed in Scilit: