# zbMATH — the first resource for mathematics

Computable symbolic dynamics. (English) Zbl 1170.03029
The paper mainly consider computable dynamical systems on the string space $$\{0,1,\dots,k\}^{\mathbb N}$$. The symbolic dynamics relative to a clopen partition is considered and several results are proved on the associated subshift. In particular, this set is proved to be an effectively closed set, and examples of $$\Pi _0^1$$ subshifts without computable elements are contructed. In the last part of the paper this framework is applied to investigate some computability question about unimodal maps and their symbolic dynamics.

##### MSC:
 03F60 Constructive and recursive analysis 03D80 Applications of computability and recursion theory 26E40 Constructive real analysis 37B10 Symbolic dynamics
##### Keywords:
computability; symbolic dynamics; computable closed sets
Full Text:
##### References:
 [1] Braverman, Computing over the reals: foundations for scientific computing, Notices Amer. Math. Soc. 53 pp 318– (2006) · Zbl 1092.68038 [2] Braverman, Non-computable Julia sets, J. Amer. Math. Soc. 19 pp 551– (2006) [3] D. Cenzer, Effective dynamics. In: Logical Methods in Honor of Anil Nerode’s Sixtieth Birthday (J. Crossley, J. Remmel, R. Shore, and M. Sweedler, eds.), pp. 162-177 (Birkhäuser, 1993). [4] D. Cenzer, $$\Pi$$01 classes in computability theory. In: Handbook of Recursion Theory (E. Griffor, ed.). Studies in Logic and Foundations of Mathematics 140, pp. 37-85 (North-Holland, 1999). · Zbl 0939.03047 [5] D. Cenzer, S. A. Dashti, and J. L. F. King, Effective symbolic dynamics. In: CCA 2007 (Computability and Complexity in Analysis, Siena, June 2007) (R. Dillhage, T. Grubb, A. Sorbi, K. Weihrauch, and N. Zhong, eds.). Informatik Berichte, Universität Hagen, 79-89 (2007) and [6] Electronic Notes in Theoretical Computer Science 202, 89-99 (2008). [7] Cenzer, Effectively closed sets and graphs of computable real functions, Theoret. Comput. Sci. 284 pp 279– (2002) · Zbl 1039.03033 [8] D. Cenzer, and J. B. Remmel, $$\Pi$$01 classes in mathematics. In: Recursive Mathematics (Y. Ersov, S. Goncharov, A. Nerode, and J. B. Remmel, eds.). Studies in Logic and Foundations of Mathematics 138, pp. 623-821 (North-Holland, 1998). · Zbl 0941.03044 [9] D. Cenzer, and J. B. Remmel, Effectively closed sets. To appear in Association for Symbolic Logic Lecture Notes. · Zbl 1140.03026 [10] P. Collet, and J. P. Eckmann, Iterated Maps On The Interval As Dynamical Systems (Birkhäuser, 1980). · Zbl 0458.58002 [11] J.-C. Delvenne, Dynamics, information and computation. Ph. D. thesis, Université Catholique de Louvain (2005). [12] Delvenne, Decidability and universality in symbolic dynamical systems, Fundamenta Informaticae 74 pp 463– (2006) · Zbl 1114.03032 [13] R. L. Devaney, An Introduction to Chaotic Dynamical Systems (Addison-Wesley, 1995). [14] Grzegorczyk, On the definitions of computable real continuous functions, Fund. Math. 44 pp 61– (1957) · Zbl 0079.24801 [15] Huang, Applications of pure recursion theory to recursive analysis, Acta Sinica 28 pp 625– (1985) · Zbl 0638.03058 [16] K. Ko, Complexity Theory of Real Functions (Birkhäuser, 1991). · Zbl 0791.03019 [17] Ko, On the computability of fractal dimensions and Julia sets, Ann. Pure Appl. Logic 93 pp 195– (1998) [18] Lacombe, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles, Comptes Rendus Acad. Sci. Paris 241 pp 2478– (1955) · Zbl 0065.00201 [19] D. Lind, and B. Marcus, An Introduction to Symbolic Dynamics and Coding (Cambridge University Press, 1995). · Zbl 1106.37301 [20] M. Lothaire, Combinatorics on Words (Addison-Wesley, 1983). · Zbl 0514.20045 [21] Metropolis, On finite limit sets for transformation of the unit interval, J. Combinatorial Theory (A) 15 pp 25– (1973) · Zbl 0259.26003 [22] R. Rettinger, and K. Weihrauch, The computational complexity of some Julia sets. In: Proc. 35th ACM Symposium on Theory of Computing (San Diego, June 2003) (M. X. Goemans, ed.), pp. 177-185 (ACM Press, 2003). · Zbl 1192.68375 [23] K. Weihrauch, Computable Analysis (Springer, 2000). · Zbl 0956.68056 [24] H. Xie, Grammatical Complexity and One-Dimensional Dynamical Systems (World Scientific, 1996). · Zbl 1368.58001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.