“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 7822 |
|
||||
| Abstract: | |||||
|
Thanks to an observation by R. Robinson, for any
positive real α the function λn.⎣nα⎦ mapping positive integers n to the integer part
⎣nα⎦ of nα (called the Beatty sequence
corresponding to α) is computable if and only if α
is (Cauchy) computable. For any α ∈ \mathbbR ≥ 0,
oracle A, and r ≥ 1, we show that λn.⎣nα⎦ has a ∆rA graph if and only if
α is of class ∆rA(\mathbbR) in the recently
introduced Zheng-Weihrauch (Z-W) hierarchy. If
α ∈ ΣrA(\mathbbR)∪ΠrA(\mathbbR),
then the above function is of class ∆r+1A. We
consider λn.⎣nα+γ⎦ and show that
the if part corresponding to the next to the last statement
still holds (when now both coefficients are in
∆rA(\mathbbR)). We prove the converse when α
is irrational. If α is rational, then the function is
always primitive recursive (even for γ's beyond the Z-W
hierarchy). Finally, we show that the set of (indices of)
computable Beatty sequences is Π2.
Download TeX format |
|||||
| back to top | |||||
