Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-22T20:57:48.882Z Has data issue: false hasContentIssue false
  • English
  • Français

Splittings of effectively speedable sets and effectively levelable sets

Published online by Cambridge University Press:  12 March 2014

Roland SH. Omanadze
Roland SH. Omanadze*
Affiliation:
I. Vekua Institute of Applied Mathematics, Tbilisi State University, Tbilisi, 0143, Georgia, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove that a computably enumerable set A is effectively speedable (effectively levelable) if and only if there exists a splitting (A0, A1) of A such that both A0 and A1 are effectively speedable (effectively levelable). These results answer two questions raised by J. B. Remmel.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 69 , Issue 1 , March 2004 , pp. 143 - 158
Copyright
Copyright © Association for Symbolic Logic 2004

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Bäuerle, F. A. and Remmel, J. B., On speedable and levelable vector spaces, Annals of Pure and Applied Logic, vol. 67 (1994), pp. 61–112.CrossRefGoogle Scholar
[2]Blum, M., A machine-independent theory of the complexity of recursive functions, Journal of the Association for Compututing Machinery, vol. 14 (1967), pp. 322–336.Google Scholar
[3]Blum, M., On the size of machines, Information and Control, vol. 11 (1967), pp. 257–265.Google Scholar
[4]Blum, M. and Marques, I., On computational complexity of recursively enumerable sets, this Journal, vol. 38 (1973), pp. 579–593.Google Scholar
[5]Downey, R. and Shore, R., Splitting theorems and the jump operator, this Journal, vol. 94 (1998), pp. 45–52.Google Scholar
[6]Downey, R. and Stob, M., Splitting theorems in recursion theory, Annals of Pure and Applied Logic, vol. 65 (1993), pp. 1–106.CrossRefGoogle Scholar
[7]Filotti, I., On effectively levelable sets, Recursive Function Theory Newsletter, vol. 2 (1972), pp. 12–13.Google Scholar
[8]Friedberg, R. M. and Rogers, H. Jr., Reducibility and completeness for sets of integers, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 5 (1959), pp. 117–125.CrossRefGoogle Scholar
[9]Gill, J. T. III and Morris, P. H., On subcreative sets and S-reducibility, this Journal, vol. 39 (1974), no. 4, pp. 669–677.Google Scholar
[10]Jahn, M. A., Implicit measuraments of dynamic complexity properties and splittings of speedable sets, this Journal, vol. 64 (1999), no. 3, pp. 1033–1064.Google Scholar
[11]Odifreddi, P., Classical recursion theory, vol. I, North-Holland Publishing Co., Amsterdam, 1989.Google Scholar
[12]Omanadze, R. Sh., On sQ-completeness of recursively enumerable sets, Matematicheskie Zametki, vol. 52 (1992), pp. 79–87, in Russian; Mathematical Notes, 1993, pp. 948–952 (English translation).Google Scholar
[13]Omanadze, R. Sh., Complexity properties of recursively enumerable sets and sQ-completeness, Matematicheskie Zametki, vol. 62 (1997), no. 3, pp. 425–429, in Russian; Mathematical Notes, pp. 356–359 (English translation).Google Scholar
[14]Omanadze, R. Sh., Quasi-degrees of recursively enumerable sets, Computability and models: Perspectives east and west (Cooper, S. B. and Goncharov, S., editors), Kluwer Academic/Plenum Publishers, New York, Boston, Dordrecht, London, Moscow, 2003.Google Scholar
[15]Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[16]Soare, R. I., Computational complexity, speedable and levelable sets, this Journal, vol. 42 (1977), pp. 545–563.Google Scholar
[17]Soare, R. I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Omega Series, Springer-Verlag, Heidelberg, 1987.CrossRefGoogle Scholar