ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ

Том 55

2019

Вып. 3

УДК 621.391.15 : 519.72

С.С. Марченков

ОБ АЛФАВИТНОМ КОДИРОВАНИИ СВЕРХСЛОВ¹

Рассматривается алфавитное кодирование сверхслов. Устанавливаются кри-

терии однозначности кодирования для случаев конечного и бесконечного кодов.

Доказывается, что в случае бесконечного кода проблема распознавания неод-

нозначности кода является m-полной в классе ∃¹∀⁰ аналитической иерархии

Клини.

Ключевые слова: алфавитное кодирование, сверхслово, аналитическая иерархия

Клини.

DOI: 10.1134/S0555292319030069

В теории кодирования хорошо известен результат Ал.А. Маркова [1-3] - кри-

терий однозначности алфавитного кодирования. Этот результат можно обобщать

на сверхслова в двух направлениях: находить критерии однозначности алфавитно-

го кодирования для кодирования сверхслов конечным кодом либо для кодирования

сверхслов бесконечным кодом. Эти два направления существенно отличаются по

сложности получаемых результатов. Если для конечного кода сложность критерия

близка к сложности критерия из [1-3], то для бесконечного кода возникают пробле-

мы, связанные как с заданием кода, так и с описанием однозначных кодов.

В данной статье мы сначала получаем критерий однозначности кода для кодиро-

вания сверхслов конечным кодом (теорема 1) и переносим его на случай бесконеч-

ных кодов (теорема 2). Затем рассматриваем сложность проблемы распознавания

однозначности бесконечного кода. В теореме 3 в терминах аналитической иерархии

Клини устанавливается “верхняя оценка” сложности этой проблемы, а в теореме 4

с использованием функциональных уравнений - такая же “нижняя оценка”.

Введем необходимые понятия. Пусть A - конечный алфавит. Через A^∗ обозначим

множество всех (конечных) слов в алфавите A, включая пустое слово Λ, а через A^∞ -

множество всех сверхслов в алфавите A (упорядоченных счетно-бесконечных по-

следовательностей, составленных из букв алфавита A). Если a ∈ A^∗, то пусть |a|

обозначает длину слова a.

Если A = {a₁, . . . , a_k} и B - алфавит, то алфавитным кодированием (из A в B)

называется отображение

ϕ: A → B^∗ \ {Λ}.

Отображение ϕ продолжается на множество A^∗: если ai1 . . .a_i

ℓ

∈ A, то

ϕ(ai1 . . . a_i

) = ϕ(ai1)...ϕ(aiℓ).

ℓ

Считается также, что ϕ(Λ) = Λ.

¹ Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных

исследований (номер проекта 19-01-00200).

Обычно в кодировании ϕ рассматривают только множество

C(ϕ) = {ϕ(a₁), . . . , ϕ(a_k)},

которое, собственно, и называют кодом. В дальнейшем код C(ϕ) будем записывать

в виде C = {C₁, . . ., C_k}. Код C называется однозначным, если различным после-

довательностям (i₁, . . . , i_m) из {1, 2, . . . , k}^∗ \ {Λ} соответствуют различные слова

Ci1 . . . Cim .

Далее будем рассматривать кодирование и декодирование сверхслов. Это означа-

ет, в частности, что последовательности (i₁, i₂, . . .) берутся из множества {1, . . . , k}^∞,

а соответствующие им сверхслова Ci1Ci2 . . . принадлежат множеству B^∞. Понятие

однозначности кода естественным образом переносится на сверхслова.

С кодом C = {C₁, . . . , C_k} свяжем множество S = {β₀, β₁, . . . , β_ℓ}, состоящее из

пустого слова Λ (считаем, что β₀ = Λ) и всех непустых слов β₁, . . . , β_ℓ, которые

одновременно являются собственными (отличными от кодовых слов) префиксами

и суффиксами подходящих кодовых слов. Определим ориентированный граф G_C

с ℓ + 1 вершинами, которые помечены словами множества S. Для упрощения изло-

жения вершины графа G_C будем отождествлять с соответствующими словами из S.

Для произвольных двух вершин β_i, β_j (допускается i = j) дуга от вершины β_i к вер-

шине β_j существует в графе G_C только в том случае, когда найдутся такие кодовые

слова C_p, Cq1 , . . . , Cqs , что

C_p = β_iCq1 . . . Cqs β_j.

При этом если i = 0 и j = 0, то возможно s = 0; если только один из индексов i, j

равен 0, то должно быть s ≥ 1; если же i = j, то должно быть s ≥ 2. Считаем,

что в случае существования дуги из вершины β_i в вершину β_j на ней выписана

соответствующая последовательность кодовых слов Cq1 . . . Cqs. Обычным образом

вводится понятие ориентированного пути в графе G_C. Длиной пути считаем число

входящих в него дуг.

Доказательство теоремы 1 проводится в духе доказательства соответствующего

результата при кодировании конечных слов [1-3].

Теорема 1. Алфавитный код C = {C₁,C₂,...,C_k} является однозначным то-

гда и только тогда, когда в графе G_C отсутствуют ориентированные пути длины

ℓ + 1, выходящие из вершины Λ.

Доказательство. Предположим сначала, что в графе G_C имеется ориенти-

рованный путь Γ длины ℓ+1, выходящий из вершины Λ. Тогда среди вершин, входя-

щих в путь Γ, по крайне мере одна вершина встречается дважды. Пусть β_i - первая

(от вершины Λ) вершина пути Γ, которая входит в путь Γ не один раз. Рассмот-

рим подпуть Γ^′ пути Γ, который начинается в вершине Λ и оканчивается вторым

вхождением вершины β_i в путь Γ. Образуем из Γ^′ бесконечный путь Δ, повторяя

после вершины β_i бесконечное число раз цикл из вершины β_i в вершину β_i. Пусть

сверхслово W получается последовательным выписыванием всех слов, стоящих в

вершинах и дугах пути Δ. Утверждается, что сверхслово W допускает по крайней

мере два декодирования.

В самом деле, предположим, что указанное сверхслово W имеет вид

β₀C⁽¹⁾¹ . . .C(1)sβj1 C(2)1 . . . C(2)sβj2 . . . βjr C(r+1)1 . . .C(r+1)s

βjr+1 . . . ,

r+1

где в сверхслове W обозначены все вхождения слов βjm из множества S и кодовых

слов Cqp) (выписанных на дугах пути Δ). Тогда согласно определению графа G_C

одно декодирование сверхслова W имеет вид

C⁽¹⁾¹ . . .C(1)sβj1 , C(2)1, . . ., C(2)s, βj2C(3)1...C(3)s

βj3 , . . .,

а другое -

C⁽¹⁾¹, . . ., C(1)s, βj1C(2)1...C(2)sβj2 , C(3)1, . . . , C(3), . . .s

Обратно, предположим, что существует сверхслово W, которое допускает два

различных декодирования:

W =Ci1Ci2...Cin ...=Cj1Cj2 ...Cjn ...

Если для двух различных последовательностей i₁, i₂, . . . , i_n и j₁, j₂, . . . , j_m выполня-

ется равенство

Ci1 Ci2 . . . Cin = Cj1 Cj2 . . .Cjm ,

(1)

то код C не является однозначным уже для слов конечной длины. Тогда, как известно

[1-3], в графе G_C существует ориентированный цикл, проходящий через вершину Λ.

Очевидно, что в этом случае в графе G_C будут существовать и ориентированные

пути сколь угодно большой длины, выходящие из вершины Λ.

Далее предполагаем, что равенство (1) не выполняется ни для каких различ-

ных последовательностей i₁, i₂, . . . , i_n и j₁, j₂, . . . , j_m. Это означает, в частности, что

при любом n конец слова Ci1Ci2 . . . Cin в сверхслове W лежит внутри некоторого

слова Cjm . То же самое справедливо и для слов Cj1 Cj2 . . . Cjm .

Рассмотрим слова Ci1 и Cj1 . При |Ci1 | = |Cj1 | получаем i₁ = j₁, и сверхслово

можно “сократить” на слово Ci1 . Поэтому при |Ci1 | > |Cj1 | слово Ci1 представимо

в виде Ci1 = Cj1 . . . Cjm β₁, где m ≥ 1 и β₁ - собственный префикс слова Cjm+1,

который, очевидно, является также собственным суффиксом слова Ci1 . В случае

|Ci1 | < |Cj1 | справедливо симметричное представление Cj1 = Ci1 . . . Cin β₁, где β₁ -

собственный префикс слова Cin+1 и собственный суффикс слова Cj1.

Таким образом, в графе G_C вершина Λ будет соединена дугой с вершиной β₁,

при этом на дуге выписано слово Cj1 . . . Cjm либо слово Ci1 . . . Cjn , составленные из

кодовых слов кода C.

Далее продолжаем по индукции. Пусть в сверхслове W уже найдено подслово β_p

(оно может совпадать с ранее найденным словом β_q), которое является как собствен-

ным префиксом кодового слова из C, так и собственным суффиксом (вообще говоря,

другого) кодового слова из C. И пусть слово β_p либо является собственным префик-

сом слова Cin+1 (входящего в начало Ci1 . . . Cin Cin+1 сверхслова W) и собственным

суффиксом слова Cjm (входящего в начало Cj1 . . . Cjm сверхслова W), либо наоборот

- собственным суффиксом слова Cin (входящего в начало Ci1 . . . Cin сверхслова W)

и собственным префиксом слова Cjm+1 (входящего в начало Cj1 . . . CjmCjm+1 сверх-

слова W ). Наконец, предположим, что в графе G_C имеется ориентированный путь,

ведущий из вершины Λ в вершину β_p.

Последующий этап доказательства использует только тот факт, что слово Cjm

заканчивается внутри слова Cin+1, имея с данным словом непустое пересечение β_p

(первый случай), или слово Cin заканчивается внутри слова Cjm+1 , пересекаясь

с этим словом по слову β_p (второй случай). Поэтому, как и в базисе индукции, рас-

сматриваем либо расположение сверхслова Cjm+1 . . . по отношению к слову Cin+1 ,

либо расположение сверхслова Cin+1 . . . по отношению к слову Cjm+1 . Соответству-

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

их опускаем. ▴

Очевидно, что на основе доказанной теоремы легко определить алгоритм про-

верки однозначности алфавитного кодирования сверхслов. Отметим еще, что в фор-

мулировке теоремы 1 можно с равным успехом говорить об отсутствии в графе G_C

ориентированных циклов, “достижимых” из вершины Λ: граф G_C имеет ℓ+1 вершин,

и потому существование в графе G_C ориентированного пути длины ℓ+1 равносильно

существованию в нем достижимого из вершины Λ ориентированного цикла.

Всюду далее мы будем рассматривать алфавитные коды C = {C₁, C₂, . . .}, со-

стоящие из бесконечного числа кодовых слов. Так же, как для конечного случая,

определяем множество S и ориентированный граф G_C. Однако теперь как множе-

ство S, так и граф G_C могут быть бесконечными. Вместе с тем кодировать кодом C

мы будем только сверхслова.

Теорема 2 представляет собой несложное обобщение теоремы 1, и потому ее до-

казательство мы не приводим.

Теорема 2. Алфавитное кодирование C = {C₁,C₂,...} является однозначным

тогда и только тогда, когда в графе G_C отсутствуют ориентированные пути

бесконечной длины, выходящие из вершины Λ.

В оставшейся части статьи мы хотим оценить сложность распознавания одно-

значности кодирования. Для этого нам придется некоторым стандартным образом

задавать бесконечные множества {C₁, C₂, . . .} кодовых слов. Примем следующее со-

глашение: множество {C₁, C₂, . . .} задается одноместной функцией f с областью

определения B^∗ (напомним, что кодовые слова C₁, C₂, . . . рассматриваются в алфа-

вите B) и областью значений {0, 1}. При этом для любого слова C ∈ B^∗ равенство

f (C) = 1 выполняется тогда и только тогда, когда C ∈ C. Таким образом, f пред-

ставляет собой характеристическую функцию кода C.

Пусть N = {0, 1, . . .}, и пусть P_N обозначает множество всех (всюду определен-

ных) функций на N. Функции из P_N будем называть функциями счетнозначной

логики. Для любого n ≥ 1 и любого множества Q ⊆ P_N обозначаем через Q(n)

множество всех n-местных функций из Q.

Обозначим через U(f) отношение “код, определяемый функцией f, не является

однозначным”. Чтобы оценить сложность отношения U(f), воспользуемся классом

∃¹∀⁰ аналитической иерархии Клини (см., например, [4]). Напомним, что класс ∃¹∀⁰

(индекс 1 означает, что квантификация проводится по функциональным перемен-

ным, а индекс 0 - по числовым) состоит из всех отношений, которые представимы

в виде

(∃¹g₁) . . . (∃¹g_m)(∀⁰y₁) . . . (∀⁰y_n)R(f₁, . . . , f_k, g₁, . . . , g_m, x₁, . . . , x_ℓ, y₁, . . . , y_n),

где f₁, . . . , f_k, g₁, . . . , g_m - переменные для функций из P_N, x₁, . . . , x_ℓ, y₁, . . . , y_n - чис-

ловые переменные, принимающие значения из N, а R - рекурсивное отношение (от

функциональных и числовых переменных).

Теорема 3. Отношение U(f) принадлежит классу ∃¹∀⁰ аналитической ие-

рархии Клини.

Доказательство. Используем критерий однозначности кода, установленный

в теореме 2. Отношение U(f) представим в форме

(∃¹g)(∀⁰y)R(f, g, y).

Содержательно функция g(y) будет определять бесконечную ветвь в дереве G_C , где

кодирование C задается функцией f. Более подробно: по каждому числу y ≥ 0

функция g будет выдавать номер (в некоторой стандартной вычислимой нумера-

ции ν множества всех упорядоченных наборов слов в алфавите B) (y + 1)-го набора

из бесконечной последовательности

(β₀, C(1)i

,...,C(1)i

,βt1), (βt1,C(2)j

,...,C(2)j

,βt2), (βt2,C(3)k

,...,C(3)k,βt3), ...,

(2)

где β₀, βt1 , βt2 , . . . - слова из множества S, построенного для кодирования C, β₀ = Λ,

C(d)ℓ - кодовые слова, и каждое из слов

β₀C(1)i

...C(1)i

βt1 , βt1 C(2)j

...C(2)j

βt2 , βt2 C(3)k

...C(3)kβt3 , . . .

(3)

также является кодовым словом. В соответствии с данным описанием для каждого y

отношение R “находит” набор слов с номером g(y), затем “проверяет”, что выбран-

ный набор имеет вид, указанный в последовательности (2). Для этого отношение R

“выполняет” следующие действия.

Прежде всего, проверяет, что все слова набора с номером g(y), отличные от перво-

го и последного слова, являются кодовыми словами. Это действие легко выполнить,

обращаясь к функции f (напомним, что f является характеристической функцией

рассматриваемого кода). Далее при y = 0 отношение R находит наборы с номерами

g(y - 1), g(y + 1) и убеждается, что последнее слово набора ν(g(y - 1)) совпадает

с первым словом набора ν(g(y)), а последнее слово данного набора - с первым словом

набора ν(g(y + 1)) (если y = 0, то первое слово набора ν(g(y)) должно быть пустым,

а последнее - совпадать с первым словом набора ν(g(1))). При этом дополнительно

проверяется, что в случае совпадения с пустым словом ровно одного из крайних

слов набора ν(g(y)) этот набор содержит не менее трех слов, а в случае совпадения

с пустым словом обоих крайних слов набора ν(g(y)) - не менее четырех. Затем отно-

шение R “склеивает” все слова набора ν(g(y)) и проверяет, что полученное слово (ко-

торое присутствует в последовательности (3)) является кодовым словом (при этом

вновь используется функция f). Заметим, что выполняемые действия гарантиру-

ют, что все непустые слова последовательности βt1 , βt2 , . . . являются одновременно

собственными префиксами и собственными суффиксами кодовых слов кода C.

Нетрудно теперь понять, что если для данной функции f (принимающей только

значения 0 и 1) найдется такая фукция g, что при любом y выполняется опре-

деленное выше отношение R(f, g, y), то функция f представляет собой характери-

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

несуществовании функции g с указанными свойствами соответствующий код будет

однозначным. ▴

Теорему 3 можно рассматривать как “оценку сверху” сложности отношения U(f).

Чтобы показать, что отношение U(f) имеет такую же “оценку снизу”, нам придется

ввести некоторую формализацию процесса “вычисления” произвольного отношения

вида

(∃¹g)(∀⁰y)R(f, g, y).

По ряду соображений технического характера нам будет удобно воспользоваться

формализмом функциональных уравнений счетнозначной логики [5,6].

Определим язык L_N функциональных уравнений. Предполагаем, что каждая

функция из P_N имеет индивидуальное обозначение. Для обозначения n-местных

функций из P_N используем символы

, которые называем функциональными кон-

стантами. Наряду с функциональными константами рассматриваем функциональ-

ные переменные. Для обозначения n-местных функциональных переменных исполь-

зуем символы ϕ(n)i. Областью значений функциональной переменной ϕ(n)i служит

множество P(n)N. В случае, когда это не приводит к недоразумению, верхние ин-

дексы у функциональных констант и функциональных переменных будем опускать.

Помимо функциональных переменных используем обычные предметные (числовые)

переменные x₁, x₂, . . . с областью значений N.

Язык L_N функциональных уравнений состоит из предметных переменных x_i

(i = 1, 2, . . . ), функциональных переменных ϕ(n)i (i, n = 1, 2, . . . ), функциональных

констант

, знака равенства = , левой и правой скобок и запятой.

Пусть Q ⊆ P_N. Определим понятие терма над Q. Всякая предметная переменная

есть терм над Q. Если t₁, . . . , t_n - термы над Q,

- функциональная константа,

служащая обозначением функции из Q, а ϕ(n)i - функциональная переменная, то

выражения

f(n)ν(t₁, . . . , t_n), ϕ(n)i(t₁, . . . , t_n)

суть термы над Q. Равенством над Q называем любое выражение вида t₁ = t₂, где

t₁, t₂ - термы над Q. Равенства над Q называем также функциональными уравне-

ниями над Q.

Пусть t₁ = t₂ - функциональное уравнение над Q, и пусть ϕ(n1)_i,...,ϕ(nm)

все функциональные переменные, входящие в уравнение t₁ = t₂. Решением урав-

нения t₁ = t₂ называем систему функций {

ν1

,...,

νm

} из P_N, которая после

замены каждой функциональной переменной ϕ(ns) соответствующей функциональ-_i

ной константой

νs превращает уравнение t1 = t2 в тождество (относительно всех

входящих в уравнение предметных переменных).

Пусть Ξ - конечная система уравнений над Q. Решением системы уравнений Ξ

называем систему функций из P_N, которая является решением каждого уравнения,

входящего в Ξ. Будем говорить, что система уравнений Ξ выполнима, если систе-

ма Ξ имеет решение. Проблема выполнимости для систем функциональных урав-

нений состоит в том, чтобы по произвольной системе функциональных уравнений

определить, является ли данная система выполнимой.

В [7] установлено, что проблема выполнимости для систем функциональных

уравнений, содержащих только функциональные константы 0, x + 1, принадлежит

классу ∃¹∀⁰ аналитической иерархии Клини. Более того, эта проблема является

m-полной в данном классе. Чтобы использовать указанную проблему в теореме 4,

нам потребуется определить так называемое дерево решений системы функциональ-

ных уравнений над множеством функциональных констант {0, x + 1}. Для произ-

вольного множества функциональных констант это сделано в работе [6]. Мы воспро-

изведем из нее основные этапы построения дерева решений применительно к мно-

жеству констант {0, x + 1}.

Итак, пусть Ξ - система функциональных уравнений, содержащая только функ-

циональные константы 0, x + 1. По системе Ξ будем строить бесконечное дерево Γ

(дерево решений системы уравнений Ξ), вершины которого также могут иметь бес-

конечную степень. В каждой вершине дерева Γ, за исключением корня, будут опре-

деляться в конечном числе точек значения всех функций, составляющих предпо-

лагаемое решение системы Ξ. В некоторых вершинах дерева Γ процесс дальнейше-

го построения дерева (из данной вершины) будет обрываться. Основное свойство

дерева Γ состоит в том, что существует взаимно-однозначное соответствие между

бесконечными ветвями дерева Γ и решениями системы уравнений Ξ.

Пусть x₁, . . . , x_n - все предметные переменные системы Ξ, ϕ₁, . . . , ϕ_m - все ее

функциональные переменные, а ϕ¹, . . . , ϕ^k - все вхождения функциональных пере-

менных в систему Ξ (некоторые функциональные переменные могут входить в си-

стему Ξ несколько раз). Зафиксируем эффективные нумерации множеств Nⁿ и N^k

(можно, например, перечислять элементы множества Nⁿ группами с одинаковым

значением суммы координат в группе и лексикографическим порядком в каждой

группе). Наборы с номером i будем обозначать через x(n)i и x(k)i соответственно.

Будем также предполагать, что x(n)0 - нулевой набор.

Дерево Γ определяется по ярусам (вершины, расположенные на одном и том же

расстоянии от корня дерева). При этом на ярусе с номером ℓ (ℓ ≥ 1) будут рассмат-

риваться набор x(n)ℓ-1 (для предметных переменных x₁, . . . , x_n) и наборы x(k)0, x(k)1, . . .

(для вхождений ϕ¹, . . . , ϕ^k функциональных переменных). На ℓ-м ярусе выполняется

попытка определить в конечном числе точек возможное решение (g₁, . . . , g_m) систе-

мы Ξ, отвечающее значениям x(n)ℓ-1 предметных переменных системы Ξ и “значениям”

x(k)0, x(k)1, . . . функциональных переменных из последовательности ϕ¹, . . . , ϕ^k.

Подробно опишем первый шаг в построении дерева Γ - определение вершин пер-

вого яруса. Придадим всем предметным переменным системы Ξ значения из набо-

ра x(n)0 (т.е. значения 0). В вершинах v₀, v₁, . . . первого яруса присвоим вхождени-

ям ϕ¹, . . . , ϕ^k значения, соответственно, из наборов x(k)0, x(k)1, . . . При этом каждый

терм системы Ξ, не начинающийся символом функциональной константы, получит

некоторое числовое значение. Если терму t уже присвоено значение a и в систе-

му Ξ входит терм t + 1, то присвоим этому терму значение a + 1 (функциональной

константе 0, естественно, присваивается значение 0). Таким образом, всем термам

системы Ξ будут присвоены значения из N.

Указанное присваивание значений термам системы Ξ может оказаться проти-

воречивым. Так, для одной и той же переменной ϕ_j за счет использования раз-

личных вхождений в последовательность ϕ¹, . . . , ϕ^k одному и тому же терму вида

ϕ_j(a₁, . . ., a_p) могут быть присвоены различные значения. Кроме того, могут ока-

заться различными и значения термов, образующих равенство системы Ξ. В этих

случаях построение дерева Γ обрываем и соответствующую вершину из дерева Γ

удаляем.

Предположим, что описанное выше “означивание” термов системы Ξ в вершине v_i

к противоречию не приводит. Тогда, очевидно, в вершине v_i для значений предмет-

ных переменных из набора x(n)0 мы имеем корректное определение (в конечном числе

точек) функций g₁, . . ., g_m, образующих возможное решение системы уравнений Ξ.

Продолжая далее по индукции, предположим, что уже определены ℓ ярусов де-

рева Γ. Выберем в ярусе ℓ некоторую вершину v_i. Предполагаем, что в вершине v_i

функции g₁, . . . , g_m (из возможного решения системы уравнений Ξ) получили кор-

ректные определения в конечном числе точек, отвечающих наборам x(n)0, . . . , x(n)ℓ-1

для предметных переменных системы Ξ и некоторым наборам x(k)i,...,x(k) дляi

ℓ

вхождений функциональных переменных в систему Ξ. Во всех вершинах v₀, v₁, . . .

яруса (ℓ+1) дерева Γ для предметных переменных системы Ξ будет рассматриваться

набор x(n)ℓ и соответственно наборы x(k)0, x(k)1, . . . для вхождений функциональных

переменных.

Определение функций g₁, . . . , g_m в вершине v_i мало отличается от аналогичного

определения на первом шаге. После присваивания значений из набора x(n)ℓ предмет-

ным переменным и значений из набора x(k)i вхождениям ϕ¹, . . . , ϕ^k функциональных

переменных проверяем корректность такого присваивания. Единственное дополни-

тельное требование - новые значения, полученные здесь для функций g₁, . . . , g_m,

необходимо проверить на совместимость со значениями этих функций, полученны-

ми на пути в вершину v_i.

Перейдем к основному свойству дерева Γ. Предположим, что в дереве Γ имеется

бесконечная ветвь Δ. Проходя по всем вершинам ветви Δ, мы получим определение

функций g₁, . . ., g_m, которые, как нетрудно видеть, образуют решение системы Ξ.

Заметим, что функции g₁, . . . , g_m на ветви Δ определяются, вообще говоря, не пол-

ностью, а лишь на некоторых подмножествах декартовых степеней множества N.

Это те минимальные (по включению) подмножества, которые необходимы для вы-

полнения всех уравнений системы Ξ. Вместе с тем значения функций g₁, . . . , g_m

вне данных подмножеств никак не сказываются на выполнимости уравнений систе-

мы Ξ (эти значения не “имплицируются” системой уравнений Ξ). Поэтому решение

g₁, . . . , g_m можно доопределить до всюду определенного решения системы уравне-

ний Ξ. Таким образом, любая бесконечная ветвь дерева Γ определяет решение си-

стемы уравнений Ξ, состоящее, вообще говоря, из частичных функций.

Обратно, предположим, что всюду определенные функции g₁, . . . , g_m образуют

решение системы уравнений Ξ. Тогда, анализируя процедуру построения дерева Γ,

нетрудно убедиться, что в дереве Γ существует бесконечная ветвь. Так, если подста-

вить в систему уравнений Ξ вместо функциональных переменных ϕ₁, . . . , ϕ_m функ-

ции g₁, . . . , g_m, а вместо всех предметных переменных - значение 0, то в некоторой

вершине v_i первого яруса дерева Γ рассматриваемый набор x(k)i будет являться на-

бором “истинных” значений всех термов системы Ξ, которые начинаются функцио-

нальными переменными. Такое же положение возникнет на втором ярусе дерева Γ,

когда будут рассматриваться вершина v_j , соединенная ребром с вершиной v_i, и на-

боры x(n)1 для предметных переменных системы Ξ и x(k)j для вхождений ее функци-

ональных переменных. В результате в дереве Γ будет выделена бесконечная ветвь,

которая соответствует решению g₁, . . . , g_m.

Отметим, что дерево Γ определяется по системе уравнений Ξ эффективно. Это

значит, что имеется алгоритм (он описан выше), который по координате произволь-

ной вершины v (координата задается системой наборов x(n)ℓ-1, x(k)i,...,x(k)) опреде-i

ℓ

ляет, принадлежит ли вершина v дереву Γ, а если принадлежит, то каковы значения

функций g₁, . . ., g_m в этой вершине.

Теорема 4. Отношение U(f) является m-полным в классе ∃¹∀⁰ аналитиче-

ской иерархии Клини.

Доказательство. В теореме 3 установлена принадлежность отношения U(f)

классу ∃¹∀⁰. Поэтому для доказательства теоремы достаточно показать, что любое

множество из класса ∃¹∀⁰ m-сводится к множеству U(f). То, что всякое множество

из класса ∃¹∀⁰ можно представить в виде множества решений подходящей системы

функциональных уравнений над множеством функциональных констант {0, x + 1},

установлено с использованием формализма Эрбрана - Гёделя в работе [7] и с исполь-

зованием формализма Клини в работе [5]. Следовательно, остается показать, как

по произвольной системе функциональных уравнений Ξ над множеством {0, x + 1}

эффективно определить характеристическую функцию f кода C, чтобы система Ξ

имела решение тогда и только тогда, когда код C не является однозначным.

Воспользуемся построенным выше деревом Γ решений системы Ξ. Итак, пред-

полагаем, что каждой вершине v яруса ℓ дерева Γ приписан набор c(v), который

состоит из набора x(n)ℓ-1 значений переменных x₁, . . . , x_n, а также всех наборов, зада-

ющих части графиков функций g₁, . . . , g_m и определенных на пути от корня дерева Γ

к вершине v. Набор из графика функции g_i, отвечающий аргументам a₁, . . . , a_t, за-

писываем в виде (a₁, . . . , a_t, g_i(a₁, . . . , a_t)). Порядок наборов в c(v) следующий: сна-

чала набор x(n)ℓ-1, затем в порядке возрастания индекса i наборы из графика функции

g_i(y₁, . . ., y_t), при этом для фиксированного i наборы из графика функции g_i упо-

рядочены в соответствии с нумерацией множества N(t).

В дальнейшем набор из c(v) будем записывать в виде слова в алфавите {0, 1, 2,

3, 4}, а именно: каждое число из N представляется в стандартной двоичной записи;

двоичные записи чисел из x(n)ℓ-1 отделяются символом 2, то же самое для двоичных

записей аргументов и значений функций в графиках функций g_i; символ 3 отделяет

“блок” x(n)ℓ-1 от графика функции g₁, а также от графиков соседних функций g_i;

символ 4 стоит после графика функции g_m.

По дереву Γ (с пометками в вершинах) определим код C(Γ). Прежде всего, для

любой вершины v первого яруса внесем в код C(Γ) слово c(v). Далее, для любой

(конечной или бесконечной) ветви v₁, v₂, . . . дерева Γ внесем в код C(Γ) слова

c(v₁)c(v₂), c(v₃)c(v₄), . . . , c(v2j-1)c(v2j ), . . . ,

которые будем называть нечетными парами (если ветвь содержит нечетное число

вершин, то заканчиваем последней нечетной парой c(v2j-1)c(v2j)). Аналогично, вно-

сим в код C(Γ) слова

c(v₂)c(v₃), c(v₄)c(v₅), . . . , c(v2j )c(v2j+1), . . . ,

которые называем четными парами (если ветвь содержит четное число вершин, то,

как и выше, заканчиваем последней четной парой c(v2j )c(v2j+1)).

Очевидно, что для любой бесконечной ветви v₁, v₂, . . . сверхслово

c(v₁)c(v₂)c(v₃)c(v₄) . . . c(v2j-1)c(v2j ) . . .

допускает два декодирования: одно - последовательными нечетными парами, а дру-

гое - словом c(v₁) и последующими четными парами.

Докажем теперь, что если имеется сверхслово W, которое допускает (в коде C(Γ))

два различных декодирования, то в дереве Γ существует бесконечная ветвь.

Вообще говоря, указанные декодирования могут давать один и тот же результат

на некотором непустом начале сверхслова W . Мы хотим исключить этот вариант

из рассмотрения (на дальнейшем построении бесконечной ветви в дереве Γ данное

преобразование не скажется). Поэтому будем предполагать, что два упомянутых

декодирования различаются уже по первым кодовым словам.

Заметим теперь, что сверхслово W не может начинаться словом вида c(v)c(v),

где v - вершина первого яруса дерева Γ. В самом деле, поскольку нечетные и четные

пары из C(Γ) имеют вид c(v_t)c(vt+1), где v_t, vt+1 - различные вершины дерева Γ,

два различных декодирования сверхслова W должны начинаться одним и тем же

кодовым словом c(v). Однако эту возможность мы исключили.

Далее замечаем, что началом сверхслова не может являться слово c(v_t), где t ≥ 2.

Действительно, если t ≥ 2, то в случае нечетного t любая из расшифровок долж-

на начинаться с одной и той же нечетной пары c(v_t)c(vt+1), что мы исключили.

Аналогичные рассуждения применимы в случае четного t.

Итак, сверхслово W начинается словом c(v₁), за которым следует слово c(v₂),

причем v₁, v₂ - вершины первого и второго ярусов дерева Γ. Следовательно, в одном

из декодирований первым кодовым словом должна быть нечетная пара c(v₁)c(v₂).

В силу сделанного выше предположения относительно сверхслова W второе деко-

дирование не может начинаться с этой нечетной пары. Значит, остается одна воз-

можность: второе декодирование начинается с кодового слова c(v₁). Тогда вторым

кодовым словом в этом декодировании должна быть, конечно, четная пара вида

c(v₂)c(v₃). Понятно, что вторым кодовым словом в первом декодировании будет

нечетная пара вида c(v₃)c(v₄), третьим кодовым словом во втором декодировании -

слово вида c(v₄)c(v₅) и т.д. ▴

Автор выражает признательность рецензенту, указавшему на пробел в доказа-

тельстве.

СПИСОК ЛИТЕРАТУРЫ

1. Марков Ал.А. Об алфавитном кодировании // ДАН СССР. 1960. Т. 132. № 3. С. 521-523.

2. Марков Ал.А. Нерекуррентное кодирование // Проблемы кибернетики. Вып. 8. М.: Физ-

матгиз, 1962. С. 169-186.

3. Марков А.А. Введение в теорию кодирования. М.: Наука, 1982.

4. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972.

5. Марченков С.С. Определимость в языке функциональных уравнений счетнозначной ло-

гики // Дискрет. матем. 2013. Т. 25. № 4. С. 13-23.

6. Марченков С.С. О сложности решения систем функциональных уравнений счетнознач-

ной логики // Дискретный анализ и исслед. опер. 2015. Т. 22. № 2. С. 49-62.

7. Марченков С.С., Калинина И.С. Оператор FE-замыкания в счетнозначной логике //

Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. киберн. 2013. № 3. С. 42-47.

Марченков Сергей Серафимович

Поступила в редакцию

Московский государственный университет им. М.В.Ломоносова,

09.01.2019

факультет вычислительной математики и кибернетики

После доработки

ssmarchen@yandex.ru

29.04.2019

Принята к публикации

14.05.2019