Article contents
A note on many·one reducibility
Published online by Cambridge University Press: 12 March 2014
Extract
In this note we partly answer a question left open in [1, p. 52] by proving the following theorem.
Theorem. Supposep0≧2, ωn+1·p0≦σ<ωn+1(p0+1). Then W(σ) is uniformly many-one reducible to W(τ) for τ≧(ωn+1·p0)+1.
To prove this theorem we need only show that there is a recursive function f(e) such that if ∣e∣<σ, then ∣f(e)<(ωn+1·p0)+1, while if ∣e∣ ≮ σ, f(e)∉W. (For the notations see [2].)
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 1964
References
- 2
- Cited by