Skip to main content
1 of 3
Jim Belk
  • 8.5k
  • 1
  • 43
  • 53

Perhaps the biggest open problem in symbolic dynamics is the equivalence problem for subshifts of finite type.

Given a finite alphabet $\mathcal{A}$ and a finite set $\mathcal{F}$ of finite words over $\mathcal{A}$ (the forbidden words), the corresponding subshift of finite type consists of

  • The space $S\subseteq \mathcal{A}^\mathbb{N}$ of all infinite words over $\mathcal{A}$ that do not have any of the forbidden words as subwords, and

  • The shift map $\sigma \colon S\to S$ defined by $\sigma(a_1a_2a_3\cdots ) = a_2a_3\cdots$.

Two subshifts $(S,\sigma)$ and $(S',\sigma')$ are equivalent if they are conjugate as dynamical systems, i.e. if there exists a homeomorphism $h\colon S\to S'$ such that $h\circ \sigma = \sigma'\circ h$.

Is there an algorithm to determine whether two subshifts of finite type $(S,\sigma)$ and $(S',\sigma')$ are equivalent?

See M. Boyle, Open problems in symbolic dynamics. Contemporary mathematics 469 (2008): 69-118.

Jim Belk
  • 8.5k
  • 1
  • 43
  • 53