Семинар лаборатории теоретической информатики: "Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts". Докладчик: А. Ромащенко
We propose necessary conditions of soficness of multidimensional shifts formulated in terms of resource-bounded Kolmogorov complexity.
Using this technique we provide examples of effective and non-sofic shifts on ZZ^2 with very low block complexity: the number of admissible patterns of size NxN grows only as a polynomial in N.