Отношение на $(\omega, <)$ промежуточного спектра степеней на конусе

Основная информация

• ID статьи: 2412.01071
• Название: A relation on (ω,<) of intermediate degree spectrum on a cone
• Авторы: Jad Damaj и Matthew Harrison-Trainor
• Классификация: math.LO (математическая логика)
• Дата публикации: 7 ноября 2025 г. (arXiv v2: 5 ноября 2025)
• Ссылка на статью: https://arxiv.org/abs/2412.01071

Аннотация

В статье исследуется проблема спектров степеней (degree spectra) отношений на линейном порядке натуральных чисел $(\omega,<)$. Для дополнительного отношения $R$ на $(\omega,<)$ (например, отношения следования) спектр степеней $R$ определяется как множество степеней Тьюринга $R$ во всех вычислимых копиях $(\omega,<)$. Известно, что спектры степеней отношений на $(\omega,<)$ разделяются на четыре класса: вычислимые степени, все c.e.-степени, все $\Delta^0_2$-степени или промежуточные спектры между c.e.-степенями и $\Delta^0_2$-степенями. Примеры первых трёх классов легко строятся, однако до недавнего времени оставался открытым вопрос о существовании отношений с промежуточным спектром "на конусе". Bazhenov и др. построили примеры промежуточных спектров, но эти примеры были "неестественными" (построены через диагонализацию, зависели от выбора кодирования Гёделя). В статье используется формализм "on-a-cone" для ограничения внимания на "естественные" отношения. Основной результат — построение естественного отношения с промежуточным спектром, основанным на структурных причинах.

Исследовательский контекст и мотивация

Основные проблемы

Статья исследует фундаментальный вопрос теории вычислимых структур: как внутренняя сложность отношения характеризуется через спектр степеней. Конкретно:

1. Проблема классификации спектров степеней: Wright доказал, что спектр степеней отношения на $(\omega,<)$ либо является одноточечным множеством (вычислимая степень), либо содержит все c.e.-степени, либо состоит из всех $\Delta^0_2$-степеней, либо находится между c.e.-степенями и $\Delta^0_2$-степенями. Примеры первых трёх классов известны, но существование истинно промежуточного спектра долгое время оставалось нерешённым.
2. Проблема естественности: Bazhenov, Kalociński и Wrocławski BKW22 построили примеры промежуточных спектров, но это построение:
   • зависит от сложных приоритетных аргументов и диагонализации
   • не канонично (зависит от выбора кодирования Гёделя)
   • не релятивизируется (не сохраняет промежуточность относительно $0'$)
   • на конусе спектр степеней вырождается в c.e.-степени
3. Формализм "на конусе": Для формализации понятия "естественного" отношения используется подход "on-a-cone", связанный с гипотезой Мартина: свойство считается "почти везде" верным, если оно выполняется на всех степенях выше некоторой степени Тьюринга. Это исключает патологические примеры, зависящие от специальных кодирований.

Научное значение

• Теоретическое значение: полная характеризация структуры спектров степеней отношений на $(\omega,<)$, ответ на фундаментальный вопрос теории вычислимых структур
• Методологическое значение: демонстрация эффективности формализма "on-a-cone" в исключении неестественных конструкций
• Технический вклад: развитие теории кодирующих последовательностей (coding sequences), которая может быть применима к другим структурам

Основные вклады

1. Главная теорема (Theorem 3.7): построена вычислимая унарная функция $f$, спектр степеней которой на конусе строго находится между c.e.-степенями и $\Delta^0_2$-степенями, с основанием конуса в вычислимой степени (то есть верно для всех оракулов)
2. Явное описание естественного отношения: функция $f$ имеет простое структурное описание — область определения разбита на циклические блоки, блоки на нечётных позициях перечисляют натуральные числа как $L_1L_2L_3\ldots$, блоки на чётных позициях перечисляют так, чтобы каждое число появлялось бесконечно часто
3. Теоремы характеризации спектра степеней:
   • Theorem 3.3: спектр степеней блочной функции содержит не-c.e.-степень тогда и только тогда, когда бесконечно много блоков вложены в более поздние блоки
   • Theorem 3.6: когда все блоки (кроме конечного числа) вложены в последующие блоки, спектр состоит из всех $\Delta^0_2$-степеней тогда и только тогда, когда существует бесконечная кодирующая последовательность
4. Результат о разнообразии (Theorem 4.17): для любого чётного ординала $\alpha \geq 6$ существует блочная функция, спектр степеней которой содержит все $\beta$-c.e.-степени ($\beta < \alpha$), но не содержит все $\alpha$-c.e.-степени, что доказывает существование несчётного числа различных спектров степеней
5. Технические инновации: введены понятия кодирующих последовательностей (coding sequences) и кодирующих деревьев (coding trees), развита теория рангов максимальных/минимальных кодирующих деревьев для точной характеризации спектров степеней

Подробное описание методов

Определение задачи

Спектр степеней (Degree Spectrum): для вычислимой структуры $\mathcal{A}$ и отношения $R$ спектр степеней определяется как $\text{DgSp}_\mathcal{A}(R) = \{\deg_T(\varphi(R)) : \mathcal{B} \text{ — вычислимая копия } \mathcal{A}, \varphi: \mathcal{A} \cong \mathcal{B}\}$

Спектр степеней на конусе: если существует $X$ такой, что для всех $Y \geq_T X$ некоторое свойство выполняется для релятивизированного спектра степеней $\text{DgSp}^Y_\mathcal{A}(R)$, то это свойство называется верным "на конусе".

Проблема промежуточного спектра: построить отношение $R$ такое, что на конусе:

• спектр степеней строго содержит все c.e.-степени (существует не-c.e.-степень)
• спектр степеней строго содержится в $\Delta^0_2$-степенях (существует $\Delta^0_2$-степень, не входящая в спектр)

Основные концепции: блочные функции и кодирующие последовательности

Блочные функции (Block Functions)

Определение 2.6: функция $f: (\omega,<) \to (\omega,<)$ называется блочной функцией, если для каждого $n$ существует интервал $[a,b]$, содержащий $n$ и замкнутый относительно $f$ и $f^{-1}$. Минимальный такой интервал называется $f$-блоком.

Ключевые свойства:

• блоки не перекрываются, область определения разбивается на объединение блоков
• каждый блок имеет конечный размер, все типы блоков можно перечислить как $I_n$
• соответствует строке $\alpha_f(i) = n$, где $I_n$ — тип $i$-го блока

Кодирующие последовательности (Coding Sequences)

Определение 3.4: последовательность интервалов $[a_1,b_1], [a_2,b_2], \ldots$ и отображения $\varphi_i: [a_i,b_i] \to [a_{i+1},b_{i+1}]$ образуют $f$-кодирующую последовательность, если:

1. каждый интервал замкнут относительно блоков
2. $\varphi_i$ — сохраняющее порядок неубывающее вложение
3. $\varphi_{i+1} \circ \varphi_i$ сохраняет $f$
4. $\varphi_1$ не сохраняет $f$ (существует $x$ такой, что $\varphi_1(f(x)) \neq f(\varphi_1(x))$)
5. $a_{i+1} > b_i$ (интервалы строго возрастают)

Интуитивное понимание: кодирующие последовательности предоставляют механизм для "кодирования" $\Delta^0_2$-множеств при построении вычислимых копий:

• когда элементы множества входят/выходят, через вставку элементов в линейный порядок изменяются интервалы, соответствующие кодируемому кортежу
• отображения на нечётных/чётных шагах чередуют сохранение/несохранение $f$, соответствуя состояниям 0/1 элементов множества
• бесконечные кодирующие последовательности позволяют элементам изменять значения бесконечное число раз ($\Delta^0_2$-свойство)

Построение промежуточного спектра степеней

Описание примера (функция из Theorem 3.7)

Последовательность блоков: $L_1, L_1, L_2, L_1, L_3, L_2, L_4, L_1, L_5, L_2, L_6, L_3, L_7, L_1, L_8, \ldots$

где $L_k$ — цикл длины $k$. Паттерн:

• нечётные позиции: $L_1, L_2, L_3, L_4, \ldots$ (возрастающее перечисление)
• чётные позиции: $L_1, L_1, L_2, L_1, L_2, L_3, \ldots$ (каждое число бесконечно часто)

Ключевые свойства:

• каждый блок появляется бесконечно часто → спектр содержит не-c.e.-степень (Theorem 3.3)
• любые два блока соседствуют не более одного раза → любая кодирующая последовательность имеет длину $\leq 5$ (связь разрывается)
• нет бесконечных кодирующих последовательностей → спектр не содержит все $\Delta^0_2$-степени (Theorem 3.6)

Доказательство включения не-c.e.-степеней (Theorem 3.3)

Достаточность (бесконечно много блоков вложены в более поздние блоки):

• для любого кортежа $c$ выбираем $a$ как больший блок размера $>1$
• доказываем, что $a$ является свободным от различий (d-free) кортежем над $c$
• для данной бескванторной формулы $\varphi(c,a,b)$, строим $a' = a+1, b' = b+1$
  • $a'$ больше не является блоком, поэтому значение $f$ на $a'$ меняется
  • для экзистенциальной формулы $\psi(c,a',b')$ находим $a'', b''$ такие, что $f$ на $c,a'',b''$ имеет то же значение, что на $c,a,b$
  • используем свойство вложения блоков: $a''$ — целевой блок вложения $a$
• по Theorem 3.2 (из HT18), спектр степеней строго содержит c.e.-степени

Доказательство того, что не содержит все $\Delta^0_2$-степени (Theorem 3.6B)

Необходимость (нет бесконечных кодирующих последовательностей):

• строим $\Delta^0_2$-множество $C$ такое, что для всех вычислимых копий $L_e \cong (\omega,<)$: $\Phi_i^{f^{L_e}} \neq C \text{ или } \Psi_j^C \neq f^{L_e}$
• стратегия требования $R_{e,i,j}$:
  1. выбираем неограниченный $x$, изначально $C(x)=0$ (фаза 0)
  2. когда появляются вычисления $\Phi_i^{f^{L_e}}(x)=C(x)$ и $\Psi_j^C[0,\ldots,m_0] = f^{L_e}[0,\ldots,m_0]$, меняем $C(x)$ (фаза 1)
  3. чередуем изменения $C(x)$ каждый раз, чтобы разрушить вычисления
• ключевой аргумент: если требование входит в произвольно много фаз, то строится бесконечная (слабая) кодирующая последовательность
  • фаза $s_n$ соответствует интервалу $[a_n, b_n]$ и отображению $\pi_{s_n}: L_e \to (\omega,<)$
  • определяем $\varphi_i = \pi_{i+1} \circ \pi_i^{-1}$
  • по свойствам вычислений, $\varphi_i$ на нечётных/чётных фазах чередуют сохранение/несохранение $f$
• по Lemma 3.5, слабая кодирующая последовательность преобразуется в сильную, противоречие

Теория кодирующих деревьев (Section 4)

Максимальное кодирующее дерево (Maximal Coding Tree)

• Определение 4.8: узлы — все конечные слабые кодирующие последовательности, отношение расширения — расширение последовательности
• Ранг: $\text{maxrank}(f) = \text{rank}(T_{\max}(f))$
• Theorem 4.9: если $\alpha = \text{maxrank}(f)$, то на конусе существует не-$\alpha$-c.e.-степень, не входящая в спектр
  • доказательство: в диагонализационном построении поддерживаем функцию ранга $r(x,s): \omega^2 \to \alpha+1$
  • каждое изменение $C(x)$ соответствует расширению кодирующей последовательности, ранг строго убывает
  • по хорошей основанности дерева, $C$ является $\alpha$-c.e.-множеством

Минимальное кодирующее дерево (Minimal Coding Tree)

• Определение 4.11: узлы — конечные сильные кодирующие последовательности, но определение ранга более сложное
• Отношение разрешения (permitting): $\sigma$ разрешает $\tau$, если:
  • последние интервалы $[a_n,b_n]$ и $[a'_n,b'_n]$ удовлетворяют $a_n < a'_n$
  • существует сохраняющее $f$ отображение $\psi: [a_n,b_n] \to [a'_n,b'_n]$, коммутирующее с $\varphi_{n-1}, \varphi'_{n-1}$
• Определение ранга: $\text{minrank}(\sigma) \geq \alpha$, если:
  • существует бесконечная последовательность $\sigma_0, \sigma_1, \ldots$, где каждая разрешает следующую
  • для всех $\beta < \alpha$ и всех $i$, существует $\tau_i$, расширяющая $\sigma_i$, с $\text{minrank}(\tau_i) \geq \beta$
• Theorem 4.12: если $\alpha = \text{minrank}(f)$, то спектр степеней содержит все $\beta$-c.e.-степени ($\beta < \alpha$)
  • доказательство: для данного $\beta$-c.e.-множества $X$ (функция ранга $r: \omega^2 \to \beta$), строим $L \cong (\omega,<)$ такую, что $f^L \equiv_T X$
  • для каждого $e$ поддерживаем кодирующую последовательность $CS_{e,s}$ с $\text{minrank}(CS_{e,s}) \geq r(e,s)$
  • когда $X(e)$ меняется, расширяем кодирующую последовательность (ранг убывает)
  • когда $X(e)$ не меняется, но требуется корректировка, переходим к разрешённой последовательности того же ранга

Результаты экспериментов (проверка теорем)

Основные результаты

1. Существование промежуточного спектра степеней (Theorem 3.7)

Функция: $f$ с последовательностью блоков $L_1L_1L_2L_1L_3L_2L_4L_1\ldots$

Проверка:

• Содержит не-c.e.-степень: каждый $L_k$ появляется бесконечно часто, удовлетворяет условиям Theorem 3.3
• Не содержит все $\Delta^0_2$-степени: любая кодирующая последовательность имеет длину $\leq 5$
  • доказательство: для любой кодирующей последовательности в $[a_1,b_1]$ или $[a_2,b_2]$ связь в $[a_2,b_2]$ или $[a_3,b_3]$ становится хрупкой
  • хрупкая связь в $[a_{i+2},b_{i+2}]$ или $[a_{i+3},b_{i+3}]$ должна разорваться
  • разорванная связь не может быть продолжена (противоречие чётности)

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

2. Разнообразие спектров степеней (Theorem 4.17)

Построение: для чётного ординала $\alpha \geq 6$ на основе дерева $T$ ранга $\alpha$ строим функцию $f$

Типы блоков: для $\sigma = \langle a_0,\ldots,a_n \rangle \in T$ определяем $B_\sigma = x_0 + L_{2\ell(\sigma|_0)+2} + \cdots + L_{2\ell(\sigma|_n)+2} + x_1 + x_2 + x_3$ где "элементы-бутерброды" $x_0,x_1,x_2,x_3$ имеют значения функции, зависящие от чётности $|\sigma|$

Последовательность блоков:

• чётные позиции: $L_1, L_3, L_5, \ldots$ (циклы нечётной длины)
• нечётные позиции: $B_{\sigma_1}, L_{j(1)}, B_{\sigma_2}, L_{j(2)}, \ldots$
  • $\sigma_1, \sigma_2, \ldots$ рекурсивно перечисляют $T$, каждый бесконечно часто
  • $j(i)$ перечисляет нечётные числа, каждое бесконечно часто, с $j(i) \leq 2i+1$

Проверка:

• Минимальный ранг $\geq \alpha$: $T$ вложено в минимальное кодирующее дерево (через естественное отображение $\sigma \mapsto [a_1,b_1],\ldots,[a_{|\sigma|},b_{|\sigma|}]$)
• Максимальный ранг $\leq \alpha$:
  • хрупкие связи имеют длину последовательности $\leq 5 < \alpha$
  • другие последовательности соответствуют путям в $T^*$ (дерево пар элементов из $T$)
  • по индукции доказываем $\text{rank}^*(T^*) \leq \alpha$ (ключевой момент: $\alpha$ чётный)

Вывод: существует несчётное число различных спектров степеней (соответствующих различным $\alpha$)

Анализ конкретного примера (Example 4.15)

Для функции $f$ из Theorem 3.7:

Ранг максимального кодирующего дерева: $\text{maxrank}(f) \leq 6$

• любая кодирующая последовательность длины 5 имеет хрупкую связь
• хрупкая связь разрывается в течение 2 шагов

Ранг минимального кодирующего дерева: $\text{minrank}(f) = 3$

• нижняя граница: для $\ell < m < n$ последовательность $[a_1,b_1]$ (тип $L_\ell$) → $[a_2,b_2]$ (тип $L_m$) → $[a_3,b_3]$ (комбинация $L_\ell$ и $L_n$) показывает ранг $\geq 3$
• верхняя граница: любая последовательность с хрупкой связью имеет ранг 0 (разрешённые последовательности имеют разорванные связи)

Вывод о спектре степеней:

• содержит все 2-c.e.-степени (по $\text{minrank}=3$)
• не содержит все 6-c.e.-степени (по $\text{maxrank} \leq 6$)
• по специальному аргументу: не содержит все 3-c.e.-степени

Связанные работы

Исторический контекст

1. Ранние работы:
   • Downey и др. DKMY09: спектры степеней унарных отношений либо вычислимы, либо состоят из всех $\Delta^0_2$-степеней
   • Knoll Kno09: исследования на $\omega$ и $\zeta$
2. Теорема классификации Wright Wri18:
   • спектр либо одноточечный, либо содержит все c.e.-степени
   • исключает промежуточные спектры между вычислимой степенью и c.e.-степенями
   • оставляет открытым вопрос: существуют ли спектры между c.e.-степенями и $\Delta^0_2$-степенями
3. Прорыв BKW BKW22:
   • первое построение унарной функции с промежуточным спектром
   • ограничения:
     • не каноничен (зависит от кодирования Гёделя)
     • не релятивизируется (на конусе вырождается в c.e.-степени)
     • зависит от невычислимости функции подсчёта
4. Формализм "на конусе":
   • происходит из гипотезы Мартина Mon19
   • Montalbán Mon13: исследование вычислимых структур на конусе
   • Harrison-Trainor HT18: первое систематическое исследование спектров степеней на конусе
   • Csima & Harrison-Trainor CHT17: категоричность степеней на конусе

Преимущества данной работы по сравнению с родственными работами

Сравнение технических вкладов

• Теория кодирующих последовательностей данной работы vs метод функций подсчёта BKW:
  • кодирующие последовательности дают геометрическую/комбинаторную интуицию
  • теория рангов кодирующих деревьев точно характеризует $\alpha$-c.e.-степени
  • позволяет систематическое построение (Theorem 4.17)

Заключение и обсуждение

Основные выводы

1. Существование: существуют естественные (на конусе) отношения с промежуточным спектром степеней
2. Разнообразие: существует несчётное число различных промежуточных спектров степеней
3. Теоремы характеризации: существование кодирующих последовательностей полностью характеризует, является ли спектр всеми $\Delta^0_2$-степенями
4. Тонкая структура: ранги минимальных/максимальных кодирующих деревьев дают верхние и нижние границы для включения $\alpha$-c.e.-степеней

Ограничения

1. Зазор между минимальным и максимальным рангами (Example 4.15):
   • $\text{minrank}(f) = 3$, но $\text{maxrank}(f) = 6$
   • спектр на самом деле не содержит все 3-c.e.-степени (требуется специальный аргумент)
   • зазор происходит из сложного поведения отношения "разрешения", не только из длины последовательности
2. Случай нечётных ординалов (Question 4.18):
   • Theorem 4.17 доказана только для чётных $\alpha \geq 6$
   • вычисление ранга для нечётных ординалов сложнее (индуктивный шаг не работает)
3. Отсутствие полной характеризации (Question 4.21):
   • минимальный/максимальный ранги дают только границы
   • точное определение того, содержит ли спектр все $\alpha$-c.e.-степени, остаётся сложным
4. Несравнимые спектры степеней (Conjecture 4.16):
   • авторы предполагают существование несравнимых спектров
   • требуется построение функций с различным "поведением разрешения"

Направления будущих исследований

1. Открытые вопросы:
   • Question 4.19: следует ли из содержания не-c.e.-степени содержание всех 2-c.e.-степеней?
   • Question 4.20: существуют ли бесконечные убывающие цепи?
   • Question 4.21: точная характеризация условий включения $\alpha$-c.e.-степеней
2. Направления обобщения:
   • расширение на другие структуры (не только $(\omega,<)$)
   • исследование отношений более высокой арности (не только унарные функции)
   • связь с другими аспектами гипотезы Мартина
3. Технические улучшения:
   • упрощение вычисления ранга кодирующих деревьев
   • развитие общей теории отношения "разрешения"
   • систематический метод построения функций с заданными свойствами спектра

Глубокая оценка

Достоинства

1. Теоретическая глубина:
   • полностью решена проблема промежуточного спектра "на конусе"
   • развита полная теоретическая база кодирующих последовательностей/деревьев
   • доказано несчётное разнообразие (Theorem 4.17)
2. Технические инновации:
   • Концепция кодирующих последовательностей: элегантно захватывает суть $\Delta^0_2$-кодирования
   • Двойственность минимального/максимального кодирующего дерева: различает "однозначное кодирование" и "независимое кодирование нескольких элементов"
   • Теория рангов: точно связывает с иерархией $\alpha$-c.e.-степеней
3. Естественность:
   • примеры имеют явное описание ($L_1L_1L_2L_1L_3L_2\ldots$)
   • все параметры вычислимы ($\alpha_f, c_f$ и т.д.)
   • полностью релятивизируемы (основание конуса — вычислимая степень)
4. Систематичность:
   • необходимые и достаточные условия (Theorems 3.3, 3.6)
   • единая база (применима ко всем блочным функциям)
   • обобщаемость (схема построения Theorem 4.17)

Недостатки

1. Техническая сложность:
   • определение ранга кодирующего дерева весьма техническое (Definition 4.11)
   • индуктивное определение минимального ранга неинтуитивно
   • доказательство Theorem 4.17 требует тонких вычислений ранга
2. Неполнота результатов:
   • проблема зазора между минимальным и максимальным рангом не решена
   • рассмотрены только чётные ординалы $\alpha$
   • полная классификация спектров степеней отсутствует
3. Ограничения примеров:
   • рассмотрены только блочные функции (специальный класс унарных функций)
   • отношения более высокой арности не исследованы
   • связь с другими структурами неясна
4. Проблемы изложения:
   • обозначения громоздки ($\pi_s, \pi_{s+1}$ и т.д.)
   • некоторые доказательства многословны (Theorem 4.17)
   • отсутствуют интуитивные диаграммы (хотя есть простые рисунки)

Влияние на область

1. Вклад в область:
   • Решение важной открытой проблемы: версия "на конусе" проблемы, поставленной Harrison-Trainor в HT18
   • Методологический вклад: демонстрация эффективности формализма "on-a-cone" в исключении патологических примеров
   • Теоретические инструменты: теория кодирующих последовательностей может быть применима к другим проблемам $\Delta^0_2$-классификации
2. Практическая ценность:
   • в основном теоретический вклад, без прямых приложений
   • но понимание спектров степеней фундаментально для теории вычислимых моделей и обратной математики
3. Воспроизводимость:
   • построение полностью явно, может быть проверено
   • доказательства достаточно детальны (хотя технически сложны)
   • не требует вычислительных экспериментов

Области применения

1. Теоретические исследования:
   • теория вычислимых структур
   • теория степеней
   • исследование свойств $\alpha$-c.e.-множеств
2. Потенциальные обобщения:
   • другие классифицируемые структуры (булевы алгебры, деревья и т.д.)
   • более высокие уровни гиперарифметической иерархии
   • проблемы кодирования в обратной математике
3. Образовательная ценность:
   • демонстрация формализации понятия "естественности"
   • сочетание приоритетных аргументов со структурными свойствами
   • продвинутые примеры в теории спектров степеней

Ключевые ссылки

1. BKW22 Bazhenov, Kalociński, Wrocławski: первый пример промежуточного спектра
2. HT18 Harrison-Trainor: систематическое исследование спектров на конусе, постановка решённой в данной работе проблемы
3. Wri18 Wright: теорема четырёхчастной классификации спектров
4. DKMY09 Downey и др.: спектры унарных отношений
5. Mar75 Martin: определённость Бореля (основание для меры Мартина)
6. AK00 Ash & Knight: стандартный справочник по теории вычислимых структур

Итоговая оценка

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

Главное достижение — развитие теории кодирующих последовательностей/деревьев, которая не только решает проблему существования, но предоставляет систематический инструмент построения и классификации (Theorem 4.17 доказывает несчётное разнообразие). Эта теоретическая база может иметь глубокое влияние на исследование спектров степеней других структур.

Основная сложность заключается в зазоре между минимальным и максимальным рангами кодирующих деревьев, а также в сложности отношения "разрешения", которое порождает нетривиальное поведение. Авторы правильно указывают, что полная характеризация спектров требует понимания этих тонких комбинаторных явлений, выходящих за рамки простого анализа длины последовательности.

В целом, это глубокая и технически совершенная работа, вносящая значительный вклад в теорию вычислимых структур и предоставляющая новые инструменты и перспективы для будущих исследований.