Dynamics and computation in functional shifts

Original · EN

We introduce a new type of shift dynamics as an extended model of symbolic dynamics, and investigate the characteristics of shift spaces from the viewpoints of both dynamics and computation. This shift dynamics is called a functional shift that is defined by a set of bi-infinite sequences of some functions on a set of symbols. To analyze the complexity of functional shifts, we measure them in terms of topological entropy, and locate their languages in the Chomsky hierarchy. %Through this study, we argue that complexity of dynamics does not correspond to that of computation. Through this study, we argue that considering functional shifts from the viewpoints of both dynamics and computation give us opposite results about the complexity of systems. We also describe a new class of shift spaces whose languages are not recursively enumerable.