• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Мероприятия

Семинар лаборатории теоретической информатики: "Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts". Докладчик: А. Ромащенко

Мероприятие завершено
На очередном семинаре лаборатории теоретической информатики в среду 16 мая состоится доклад 
Андрея Ромащенко
"Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts"
Время проведения:18:10 - 19:30
Адрес мероприятия: Кочновский проезд, д. 3, ауд. 503
Заказ пропуска: evavilova@hse.ru

Аннотация

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.