# zbMATH — the first resource for mathematics

Effective symbolic dynamics. (English) Zbl 1262.37008
Dilhage, R. (ed.) et al., Proceedings of the fourth international conference on computability and complexity in analysis (CCA 2007), Siena, Italy, June 16–18, 2007. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 202, 89-99 (2008).
Summary: We investigate computable subshifts and the connection with effective symbolic dynamics. It is shown that a decidable $$\Pi_{1}^{0}$$ class $$P$$ is a subshift if and only if there is a computable function $$F$$ mapping $$2^{\mathbb{N}}$$ to $$2^{\mathbb{N}}$$ such that $$P$$ is the set of itineraries of elements of $$2^{\mathbb{N}}$$. A $$\Pi_{1}^{0}$$ subshift is constructed which has no computable element. We also consider the symbolic dynamics of maps on the unit interval.
For the entire collection see [Zbl 1172.03301].

##### MSC:
 37B10 Symbolic dynamics 03D45 Theory of numerations, effectively presented structures 03D78 Computation over the reals, computable analysis
##### Keywords:
computability; symbolic dynamics; $$\Pi_1^0$$ classes
Full Text:
##### References:
 [1] Braverman, M.; Yampolski, M., Non-computable Julia sets, J. amer. math. soc., 19, 551-578, (2006) · Zbl 1099.37042 [2] Cenzer, D., Effective dynamics, (), 162-177 · Zbl 0823.03034 [3] Cenzer, D.; Remmel, J.B., $$\operatorname{\Pi}_1^0$$ classes in mathematics, (), 623-821 · Zbl 0941.03044 [4] Cenzer, D. and J.B. Remmel, “Effectively closed sets”, Association for Symbolic Logic Lecture Notes, to appear · Zbl 1140.03026 [5] Collet, P.; Eckmann, J.P., Iterated maps on the interval As dynamical systems, (1980), Birkhuser · Zbl 0441.58011 [6] Delvenne, J.-C. “Dynamics, Information and Computation”, Ph. D. thesis, Universite Catholique De Louvain (2005) [7] Delvenne, J.-C.; Kurka, P.; Blondel, V., Decidability and universality in symbolic dynamical systems, Fund. informaticae, 74, 463-490, (2006) · Zbl 1114.03032 [8] Grzegorczyk, A., On the definitions of computable real continuous functions, Fund. math., 44, 61-71, (1957) · Zbl 0079.24801 [9] Huang, W.; Nerode, A., Applications of pure recursion theory to recursive analysis, Acta sinica, 28, 625-636, (1985) · Zbl 0638.03058 [10] Ko, K., Complexity theory of real functions, (1991), Birkhauser [11] Ko, K., On the computability of fractal dimensions and Julia sets, Ann. pure appl. logic, 93, 195-216, (1998) · Zbl 0926.03049 [12] LaCombe, D., Extension de la notion de fonction recursive aux d’une ou plusieurs variables reelles, Comptes rendus acad. sci. Paris, 241, 2478-2480, (1955) · Zbl 0065.00201 [13] Lind, D.; Marcus, B., An introduction to symbolic dynamics and coding, (1995), Cambridge University Press · Zbl 1106.37301 [14] Metropolis, N.; Stein, M.L.; Stein, P.R., On finite limit sets for transformation of the unit interval, Journal of combinatorial theory (A), 15, 25-44, (1973) · Zbl 0259.26003 [15] Rettinger, R.; Weihrauch, K., The computational complexity of some Julia sets, (), 177-185 · Zbl 1192.68375 [16] Weihrauch, K., Computable analysis, (2000), Springer · Zbl 0956.68056 [17] Xie, H., Grammatical complexity and one-dimensional dynamical systems, (1996), World Scientific · 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.