Premium
Computable symbolic dynamics
Author(s) -
Cenzer Douglas,
Dashti S. Ali,
King Jonathan L. F.
Publication year - 2008
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200710066
Subject(s) - decidability , computable function , symbolic dynamics , unit interval , mathematics , class (philosophy) , interval (graph theory) , set (abstract data type) , function (biology) , discrete mathematics , pure mathematics , combinatorics , computer science , artificial intelligence , programming language , evolutionary biology , biology
We investigate computable subshifts and the connection with effective symbolic dynamics. It is shown that a decidable Π 0 1 class P is a subshift if and only if there exists a computable function F mapping 2 ℕ to 2 ℕ such that P is the set of itineraries of elements of 2 ℕ . Π 0 1 subshifts are constructed in 2 ℕ and in 2 ℤ which have no computable elements. We also consider the symbolic dynamics of maps on the unit interval. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)