Бесшумное кодирование комбинаторных источников, хаусдорфова размерность и колмогоровская сложность

Рассматривается задача бесшумного кодирования комбинаторных (невероятностных) источников. Показано, что стоимость оптимального кода равна хаусдорфовой размерности источника. Та же задача решается при алгоритмических ограничениях на код в двух постановках: кодирование и декодирование реализуются машинами Тьюринга и конечными автоматами. Для них найдены нижние границы стоимости кода, выражаемые через колмогоровскую сложность и квазиэнтропию соответственно. Построены оптимальные коды для источников, порождаемых формальными грамматиками.