О понятии равносильности недоопределённых алфавитов

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