“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 ∆_{r}^{A} graph if and only if
α is of class ∆_{r}^{A}(\mathbbR) in the recently
introduced ZhengWeihrauch (ZW) hierarchy. If
α ∈ Σ_{r}^{A}(\mathbbR)∪Π_{r}^{A}(\mathbbR),
then the above function is of class ∆_{r+1}^{A}. 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
∆_{r}^{A}(\mathbbR)). We prove the converse when α
is irrational. If α is rational, then the function is
always primitive recursive (even for γ's beyond the ZW
hierarchy). Finally, we show that the set of (indices of)
computable Beatty sequences is Π_{2}.
Download TeX format 

back to top 