Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-28T03:59:46.425Z Has data issue: false hasContentIssue false
  • English
  • Français

Splitting theorems for speed-up related to order of enumeration1

Published online by Cambridge University Press:  12 March 2014

A. M. Dawes
A. M. Dawes*
Affiliation:
University of Western Ontario, London, CanadaN6A5B9
Get access Rights & Permissions [Opens in a new window]

Abstract

It is known from work of P. Young that there are recursively enumerable sets which have optimal orders for enumeration, and also that there are sets which fail to have such orders in a strong sense. It is shown that both these properties are widespread in the class of recursively enumerable sets. In fact, any infinite recursively enumerable set can be split into two sets each of which has the property under consideration. A corollary to this result is that there are recursive sets with no optimal order of enumeration.

Keywords

Speed-upenumeration techniquesplitting theoremorder of enumerationcomplexity measure
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 47 , Issue 1 , March 1982 , pp. 1 - 7
Copyright
Copyright © Association for Symbolic Logic 1982

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.)

Footnotes

1

This research was partially supported by NRC grant A8547.

References

REFERENCES

[1]Blum, M., A machine-independent theory of computational complexity, Journal of the Association for Computing Machinery, vol. 14 (1967), pp. 322–336.CrossRefGoogle Scholar
[2]Helm, J., Meyer, A. and Young, P., On orders of translations and enumerations, Pacific Journal of Mathematics, vol. 46 (1973), pp. 185–195.CrossRefGoogle Scholar
[3]Meyer, A. and Fischer, P., Computational speed-up by effective operators, this Journal, vol. 37 (1972), pp. 55–68.Google Scholar
[4]Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[5]Young, P., Toward a theory of enumerations, Journal of the Association for Computing Machinery, vol. 16 (1969), pp. 328–348.CrossRefGoogle Scholar
[6]Young, P., Speed-ups by changing the order in which sets are enumerated, Mathematical systems theory, vol. 5 (1971), pp. 148–156.CrossRefGoogle Scholar