Special Session 5: Scientific Computation and Numerical Algorithms

Universality in multi-dimensional shifts of finite type

Linda Westrick
Penn State University
USA
Co-Author(s):    
Abstract:
It is well-known that multidimensional shifts of finite type (SFTs) can sometimes display universal behavior, due to the arbitrary computations which can be encoded in their dynamics. We present another example: there are $\mathbb Z^2$-SFTs at every computable ordinal level of the hierarchy of topological completely positive entropy (TCPE). This answers a question of Barbieri and Garc\`ia-Ramos, who asked if there was a $\mathbb Z^2$-SFT at level 3. Furthermore, we show the property of TCPE in $\mathbb Z^2$-SFTs is coanalytic complete. Thus there is no simpler description of TCPE in $\mathbb Z^2$-SFTs than in the general case.