Abstract
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 globally admissible patterns of size $n\times n$ grows only as a polynomial in $n$. We also show that more conventional proofs of non-soficness for multi-dimensional effective shifts can be expressed interms of Kolmogorov complexity with unbounded computational resources. We also show that more conventional proofs of non-soficness for multi-dimensional effective shifts, including the techniques of Pavlov [Proc. AMS,141(3):987-996, 2013] and Kass and Madden [Proc. AMS, 141(11):3803-3816, 2013], can be expressedin terms of Kolmogorov complexity with unbounded computational resources.