Эффективно нулевые множества по Мартин-Лёфу

[Anton_Peplov]

Читаю книгу
Верещагин, Успенский, Шень. Колмогоровская сложность и алгоритмическая вероятность. М.: МЦНМО, 2013.
И вот на с. 69 встретилось мне непонятное.

Сначала дам несколько определений, чтобы стал ясен контекст.

Назовем двоичным словом кортеж нулей и единиц, двоичной последовательностью - бесконечную последовательность нулей и единиц. Рассмотрим пространство всех двоичных последовательностей $\Omega$. Назовем двоичную последовательность продолжением слова $x$, если она начинается со слова $x$. Обозначим $\Omega_x$ множество всех продолжений слова $x$. Легко показать, что система $\{\Omega_x\}$ для всевозможных $x$ образует в $\Omega$ базу топологии, и что эта топология является также кольцом множеств.

Рассмотрим функцию $p(x) = 2^{-L(x)}$, где $L(x)$ - длина слова $x$.
Определим функцию множества $m(\Omega_x) = p(x)$. Можно показать, что такая функция является мерой, заданной на кольце всех открытых множеств (откуда ее можно продолжить по Лебегу с образованием соответствующей сигма-алгебры). Кстати говоря, указанная топология метризуема как раз метрикой $d(\omega_1, \omega_2) = 2^{-n}$, где $n$ - номер (начиная с нуля) первого знака, в котором различаются последовательности $\omega_1$ и $\omega_2$. Множество $\Omega_x$ представляет собой открытый шар, причем каждая точка этого шара является его центром.

Теперь вопрос. Как известно, множество имеет нулевую меру, если для каждого $\varepsilon > 0$ найдется его покрытие мерой меньше $\varepsilon$. Как построить конструктивный вариант этого понятия? Ясно, что действительные $\varepsilon$ можно заменить рациональными. Вывести $\Omega_x$ в качестве выходных данных алгоритма тоже просто - достаточно вывести $x$.
Так вот Верещагин и К. дают такое определение.

"Множество $A$ называется эффективно нулевым (по данной мере), если существует вычислимая функция $x(\varepsilon, n)$ двух аргументов (первый - положительное рациональное число, второй - натуральное число), значениями которой являются двоичные слова, причём
1) $A \subset \Omega_{x(\varepsilon, 0)} \cup \Omega_{x(\varepsilon, 1)} \cup \Omega_{x(\varepsilon, 2)} \cup... $
2) $p(x(\varepsilon, 0)) + p(x(\varepsilon, 1)) + p(x(\varepsilon, 2)) + ... \leqslant \varepsilon $

При этом мы не требуем (выделение мое), чтобы функция $x$ была всюду определена; если $x(\varepsilon, n)$ не определено, то соответствующий член (в обоих условиях) пропускается".

И далее задача: "Покажите, что определение не изменится, если предполагать, что алгоритм получает на вход рациональное $ \varepsilon> 0$, а на выходе перечисляет некоторое множество двоичных слов (печатая их одно за другим с произвольными пробелами), которые образуют покрытие интервалами с суммарной мерой (мерой объединения) не больше $\varepsilon$".

Собственно, вопрос. Что-то мне совсем не ясна природа этого разрешения - "функция $x(\varepsilon, n)$ может быть не всюду определена". Вычислимая функция называется не определенной в точке $n$, если вычисляющий ее алгоритм, получив на вход $n$, зацикливается. Как тогда можно построить алгоритм, который строит покрытие по данному $ \varepsilon$? По идее, он должен вычислить и вывести сначала $\Omega_{x(\varepsilon, 0)}$, потом $\Omega_{x(\varepsilon, 1)}$ и так далее. Но тогда он зациклится на первом же $n$, для которого функция не определена, и получится не "соответствующий член пропускается", а просто "последовательность обрывается на предыдущем члене". Некоторый смысл этому можно придать, если потребовать, чтобы функция, не определенная в $(\varepsilon, N)$, была не определена и во всяком $(\varepsilon, n > N)$ - тогда функция зациклится если и только если она вывела последний член конечного покрытия. Но авторы такого требования не заявляют. Или тут используется тот факт, что область определения всякой вычислимой функции перечислима, и, значит, есть алгоритм $B(k)$, который для всякого натурального $k$ выдает $k$-тое по счету натуральное число $n$, для которого $x(\varepsilon, n)$ определена? Тогда почему сразу не встроить этот алгоритм в алгоритм вычисления $x(\varepsilon, n)$, потребовав, чтобы $x(\varepsilon, n)$ выдавала $n$-ный член покрытия? Это естественнее, чем разрешать ей быть не всюду определенной...

В общем, чего-то я не понимаю во всей этой истории.

[grizzly]

Anton_Peplov в сообщении #1055274 писал(а):

По идее, он должен вычислить и вывести сначала $\Omega_{x(\varepsilon, 0)}$, потом $\Omega_{x(\varepsilon, 1)}$ и так далее.

Я могу представить себе несколько вариантов решения такого вопроса. Например, мы можем после каждого этапа работы алгоритма получить заполненными бесконечное множество значений -- двоичных слов (не обязательно последовательных). Тогда через конечное число этапов мы можем получить нужное покрытие, а какие-то значения останутся ненайденными (по разным причинам).
Другой вариант: мы можем после каждого этапа получать какое-то множество цифр (не обязательно конечное) для множества (или всех) значений -- двоичных последовательностей. Например, на первом этапе определить все значения, у которых на первом месте стоит 0; или 1 на всех нечётных местах и т.п. В конце концов получим покрытие, а какие-то значения останутся незавершёнными.

Но это я фантазирую, опираясь не на знания предмета, а только на приведенные цитаты.

[Anton_Peplov]

grizzly в сообщении #1055292 писал(а):

Я могу представить себе несколько вариантов решения такого вопроса.

Ну, в общем, я следом этот вопрос и решил, вспомнив, что область применимости любого алгоритма перечислима. Чтобы получить по данному $k$ $k$-тый член покрытия, берем алгоритм, перечисляющий область определения $x(n, \varepsilon)$ при данном $\varepsilon$, и запускаем его со всеми натуральными числами до получения $k$ разных значений, а потом применяем к $k$-тому значению алгоритм вычисления $x(n, \varepsilon)$. Правда, такой алгоритм будет зацикливаться на конечных покрытиях длины $N$, когда его попросят выдать $N+1$-ый член покрытия.