Колмогоровская сложность и $VC$ размерность семейств рекурсивных функций

В. И. Донской

Крымский федеральный университет им. В. И. Вернадского, Таврическая академия, факультет математики и информатики, просп. Академика Вернадского, 4, Симферополь, 295007, Российская Федерация

Аннотация: Изучается связь между комбинаторной размерностью ($VCD$) Вапника-Червоненкиса и колмогоровской сложностью семейств частично рекурсивных функций. Для произвольного семейства частично рекурсивных функций $\mathfrak{F}$ дано определение колмогоровской сложности $KC(\mathfrak{F})$. Доказано неравенство $VCD(\mathfrak{F})\leq KC(\mathfrak{F})$, на основе которого обоснован $pVCD$ метод получения оценок размерности Вапника-Червоненкиса для произвольных семейств частично рекурсивных функций. Приведены примеры оценивания при помощи $pVCD$ метода.

Ключевые слова: $VC$ размерность, колмогоровская сложность, рекурсивные функции.

УДК: 519.7

MSC: 68R01