Effective Symbolic Dynamics
Douglas Cenzer, S. Ali Dashti, Jonathan L. F. King · Electronic Notes in Theoretical Computer Science · 2008
We investigate computable subshifts and the connection with effective symbolic dynamics. It is shown that a decidable Π10 class P is a subshift if and only if there is a computable function F mapping 2N to 2N such that P is the set of itineraries of elements of 2N. A Π10 subshift is constructed which has no computable element. We also consider the symbolic dynamics of maps on the unit interval.