  We suggest necessary conditions of soficness of multidimensional shifts
formulated in termsof resource-bounded Kolmogorov complexity. Using this
technique we provide examples ofeffective and non-sofic shifts on
$\mathbb{Z}^2$ with very low block complexity: the number of globallyadmissible
patterns of size $n\times n$ grows only as a polynomial in $n$. We also show
that moreconventional proofs of non-soficness for multi-dimensional effective
shifts can be expressed interms of Kolmogorov complexity with unbounded
computational resources.
