Seminar of the laboratory: "Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts". Lecturer: A. Romashchenko
Event ended
On May 16, 2018 Andrey Romashchenko will give a lecture "Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts".
Address: Faculty of computer science HSE, Kochnovsky proezd, 3.
Language: English
Time: 18:10-19:30
Hall: 503
If you have questions, please contact the manager of the laboratory Ekaterina Vavilova: evavilova@hse.ru.
Language: English
Time: 18:10-19:30
Hall: 503
If you have questions, please contact the manager of the laboratory Ekaterina Vavilova: evavilova@hse.ru.
Abstract
We propose necessary conditions of soficness of multidimensional shifts formulated in terms of resource-bounded Kolmogorov complexity.
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.
Date
16 May
18:10