Главная | Обратная связь | Поможем написать вашу работу!

Кодирование слов. О минимальной длине кода слова.

Пусть и . Под кодом слова мы будем понимать любое другое слово , по которому слово можно восстановить однозначно. Например, если — бинарное слово длины и — номера единиц слова , то по слову слово можно восстановить однозначно. Следующее определение связывает слова и слова.

Определение. (А.Н. Колмогорова.) Пусть — произвольная частично-рекурсивная функция (Машина Тьюринга). Тогда «сложность» слова по есть следующая величина:

(4.3)

Любое слово , удовлетворяющее условию (4.3), называется кодом или программой для слова .

Таким образом, согласно (4.3), для восстановления «сложных» слов нужны длинные программы, а «простые» слова имеют короткие коды. Однако это определение включает в себя некоторый произвол, связанный с функцией . Этот произвол состоит в том, что мы имеем дело с определённой машиной Тьюринга(Т-М). Таким образом, если , то является кодом слова относительно Т-М, обозначаемой через . Длина самого короткого кода обозначается через . Существование универсальной машины Тьюринга позволяет, в определённой степени, получить меру сложности, инвариантную относительно .

Теорема. Существует такая машина Тьюринга , что

где константа зависит лишь от МТ .

Казалось бы, что мера (4.3) позволяет адекватно и конструктивно оценивать алгоритмическую сложность кодирования произвольного слова. Однако это не совсем так, в силу следующего утверждения.

Теорема. Функция , измеряющая сложность слова относительно какой-нибудь универсальной машины Тьюринга, является алгоритмически неразрешимой.

Доказательство. Рассмотрим бинарный алфавит и упорядочим все слова из сначала по длине, а потом по возрастанию (лексикографически).

Если существует Т-М , которая вычисляет , то существует и Т-М , которая «переводит» любое натуральное число в первое по порядку (*) слово такое, что . Но тогда по числу можно восстановить слово , то есть является кодом слова . Так как длина есть , то справедливо неравенство . Противоречие.

Замечание. Нетрудно понять, что существует лишь конечное число слов, сложность которых равна . Действительно, если не так, то существуют слова, имеющие одинаковые коды, что противоречит условию однозначности кодирования.

Пусть — конечное множество. Под кодированием понимается любое инъективное отображение в некоторое множество бинарных слов. Другими словами, мы рассматриваем отображения вида :

где и при .

Длина кода слова — это, по определению, длина слова , то есть . Для того чтобы различать элементы множества , коды этих элементов должны иметь определённые ограничения на длину. Точный смысл этого замечания состоит в следующем.