  In this manuscript we study properties of multidimensional shifts. More
precisely, we study the necessary and sufficient conditions for a shift to be
sofic, i.e. the boundary between sofic shifts and effective ones. To this end,
we use different versions of algorithmic complexity (a.k.a. Kolmogorov
complexity). In the first part of the work we suggest new necessary conditions
of soficness for multidimensional shift. These conditions are expressed in
terms of Kolmogorov complexity with bounded ressources. We discuss several
applications of this technique. In particular, we construct an example of a
two-dimensional effective and non sofic shift that has a very low combinatorial
complexity : the number of global admissible N x N patterns grows only
polynomially in N. We also show that the technique developed by S.Kass and
K.Madden is equivalent to a special case of our method. In the second part, we
discuss properties of subshifts defined in terms of density of letters. More
specifically, we study two-dimensional subshifts $S(\rho)$ in the binary
alphabet (white and black cells) where a configuration is admissible if every
pattern of size N x N contains at most $N^\rho$ black cells. We show that
$S(^\rho)$ is sofic for every $\rho<1$. Moreover, all effectif subshifts of
these shifts are also sofic. The proof of this result is principally based on
the construction of a self-simulating point-fixed tile set, with several new
ingredients: an ad hoc model of computation based on a non deterministic
cellular automaton (which allows to implement efficiently massively parallel
calculations) and some properties of flows in a specific type of planar graphs.
