“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 7822
School of Mathematics
  Title:   Beatty sequences and the arithmetical hierarchy
  Author(s): 
1.  M. Ghasemi
2.  Moj. Moniri
  Status:   Published
  Journal: Lect. Notes Log.
  Vol.:  26
  Year:  2006
  Pages:   126-133
  Supported by:  IPM
  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
scroll left or right