Бывают ситуации, когда существование объекта с какими-то свойствами доказать легко, но это доказательство неконструктивно (не даёт возможности предъявить такой объект). Например, можно установить, что число всех объектов определённого вида, не обладающих нужным свойством, меньше числа всех объектов этого вида. Это можно переформулировать в терминах вероятности, а также в терминах сложности описания (плохие объекты можно коротко описать, поэтому их мало). Мы рассмотрим простые примеры такого рода, а также более сложную вероятностную технику, называемую "леммой Ловаса", а также вероятностный алгоритм построения объектов, придуманный Мозером и модифицированный Тардошем, и его следствия (слова без запрещённых подслов и другие применения).

Задачи Вопросы по рассказанному и решения этих задач можно посылать по адресу sasha.shen@gmail.com — информацию о решённых задачах я перешлю в computer science center. (Предупреждение: несколько последних задач я решать не умею и потому особенно заинтересован в их решениях.)

1. Докажите, что если множество $A$ натуральных чисел неразрешимо, то вероятность события ``$A$ сводится по Тьюрингу к случайной последовательности битов'' (т.е. существует машина с оракулом, которая разрешает $A$, если использовать эту последовательность как оракул) равна $0$.
2. Пусть мы хотим применить критерий Миллера и других к построению последовательности в двоичном алфавите, не содержащей кубов слов длины $n$ (это длина слова, куб имеет длину $3n$) и больше. При каких $n$ это удастся сделать?
3. Докажите, что если для каждого $k$ алгоритмически указан список из не более чем $2^{0.99k}$ слов длины $k$, то можно найти число $N$ и вычислимую двустороннюю последовательность, в которой нет запрещённых слов длины $N$ и более.
4. Докажите, что если у степенного ряда для $\frac{1}{1-2x+F_2x^2+F_3x^3+\ldots},$ где $F_2,F_3,\ldots$ --- количества запрещённых слов длин $2,3,\ldots$ (запрещённых слов меньших длин нет) все коэффициенты положительны, то существуют сколь угодно длинные слова без запрещённых подслов.
5. (Продолжение) Можно ли как-то связать предыдущий критерий с критерием Миллера (в знаменателе как раз стоит то самое выражение!)?
6. Попытаться вывести критерий Миллера (с тем же или более слабым условием) с помощью леммы Ловаса.
7. Попытаться переформулировать доказательство алгоритма Мозера--Тардоша в общем (или чуть менее общем) случае в терминах сжатия случайных битов.

Ссылки

1. http://arxiv.org/abs/1305.1535: бесконечная вычислимая лемма Ловаса (и изложение доказательства Мозера--Тардоша в общем случае), а также обсуждение задачи о фейрверках.
2. http://www.lirmm.fr/~ashen/kolmbook.pdf: книжка по колмогоровской сложности, там есть классической доказательство леммы Ловаса (неконструкструктивное), критерия Миллера, доказательства со сжатием для случая $n$-кнф и некоторая общая информация о вероятностных алгоритмах и выходных распределениях.