Hostname: page-component-8448b6f56d-jr42d Total loading time: 0 Render date: 2024-04-16T16:13:58.360Z Has data issue: false hasContentIssue false
  • English
  • Français

A cardinality version of Beigel's nonspeedup theorem

Published online by Cambridge University Press:  12 March 2014

James C. Owings Jr.
James C. Owings Jr.*
Affiliation:
Department of Mathematics, University of Maryland, College Park, Maryland 20742 University of Newcastle, Newcastle, New South Wales 2308, Australia
Get access Rights & Permissions [Opens in a new window]

Abstract

If S is a finite set, let ∣S∣ be the cardinality of S. We show that if m ∈ ω, A ⊆ ω, B ⊆ ω, and ∣i: ≤ i ≤ 2m & xi ∈ A}∣ can be computed by an algorithm which, for all x1, …, x2m, makes at most m queries to B, then A is recursive in the halting set K. If m = 1, we show that A is recursive.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 54 , Issue 3 , September 1989 , pp. 761 - 767
Copyright
Copyright © Association for Symbolic Logic 1989

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]Beigel, R., Query-limited reducibilities, Ph.D. thesis, Stanford University, Stanford, California, 1986.Google Scholar
[2]Beigel, R.et al., Terse, superterse, and verbose sets (to appear).Google Scholar
[3]Cenzer, D.et al., Members of countable Π10 classes, Annals of Pure and Applied Logic, vol. 31 (1986), pp. 145–163.CrossRefGoogle Scholar
[4]Epstein, R. L., Degrees of unsohability: structure and theory, Springer-Verlag, Berlin, 1979.CrossRefGoogle Scholar
[5]Kunen, K., Set theory: an introduction to independence proofs, North-Holland, Amsterdam, 1980.Google Scholar
[6]Rogers, Hartley Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[7]Shoenfield, J. R., Degrees of unsohability, North-Holland, Amsterdam, 1971.Google Scholar