Beta-shifts, their languages and computability
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Beta-shifts, their languages and computability. / Simonsen, Jakob Grue.
I: Theory of Computing Systems, Bind 48, Nr. 2, 2011, s. 297-318.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Beta-shifts, their languages and computability
AU - Simonsen, Jakob Grue
PY - 2011
Y1 - 2011
N2 - For every real number ß >1, the ß-shift is a dynamical system describing iterations of the map x ¿ ßx mod 1 and is studied intensively in number theory. Each ß-shift has an associated language of finite strings of characters; properties of this language are studied for the additional insight they give into the dynamics of the underlying system. We prove that the language of the ß-shift is recursive iff ß is a computable real number. That fact yields a precise characterization of the reals: The real numbers ß for which we can compute arbitrarily good approximations—hence in particular the numbers for which we can compute their expansion to some base—are precisely those for which there exists a program that decides for any finite sequence of digits whether the sequence occurs as a subword of some element of the ß-shift. While the “only if” part of the proof of the above result is constructive, the “if” part is not. We show that no constructive proof of the “if” part exists. Hence, there exists no algorithm that transforms a program computing arbitrarily good approximations of a real number ß into a program deciding the language of the ß-shift.
AB - For every real number ß >1, the ß-shift is a dynamical system describing iterations of the map x ¿ ßx mod 1 and is studied intensively in number theory. Each ß-shift has an associated language of finite strings of characters; properties of this language are studied for the additional insight they give into the dynamics of the underlying system. We prove that the language of the ß-shift is recursive iff ß is a computable real number. That fact yields a precise characterization of the reals: The real numbers ß for which we can compute arbitrarily good approximations—hence in particular the numbers for which we can compute their expansion to some base—are precisely those for which there exists a program that decides for any finite sequence of digits whether the sequence occurs as a subword of some element of the ß-shift. While the “only if” part of the proof of the above result is constructive, the “if” part is not. We show that no constructive proof of the “if” part exists. Hence, there exists no algorithm that transforms a program computing arbitrarily good approximations of a real number ß into a program deciding the language of the ß-shift.
U2 - 10.1007/s00224-009-9245-z
DO - 10.1007/s00224-009-9245-z
M3 - Journal article
VL - 48
SP - 297
EP - 318
JO - Theory of Computing Systems
JF - Theory of Computing Systems
SN - 1432-4350
IS - 2
ER -
ID: 37440983