Pascal Vanier (GREYC, Caen)

We will focus in this talk on different conjugacy invariants of subshifts and their links to computation. Historically, the first conjugacy invariant that was linked to computation is the entropy, which was characterized by means of their computability [Hochman and Meyerovitch 2010] afterwards, many other conjugacy invariants were characterized by means link to computational hardness : other growth invariants, number of finite orbits. Here we will briefly recall some of these results and then consider the computability of the points of a subshift itself as a conjugacy invariant through the Turing degree spectrum of a subshift, we will finish the talk by investigating its the factor complexity (the growth of the number of patterns) in the one dimensional case.