Оригинал (auto-bio.txt) был написан для заявки на какой-то американский грант в начале 1990-х (перевод на русский Шеня 15.04.2007) Краткое описание моей научной деятельности Будучи студентом, я изучал применения конечных автоматов к разрешению монадических теорий. Известное доказательство Рабина разрешимости монадической теории бесконечного дерева использовало трансфинитную индукцию, и Рабин сформулировал задачу: доказать тот же результат элементарными способами. Это было сделано мной и независимо (другим способом) Гуревичем и Харрингтоном. Моё доказательство было опубликовано в Bulletin of the European Association for Theoretical Computer Science. Шелах и Ступ обобщили теорему Рабина на деревья с бесконечным ветвлением. Мой метод позволяет добавить к результату Шелаха и Ступа отношения, связывающие различные уровни дерева. Я также изучал сложность конечных автоматов, которые соответствуют монадическим формулам. Следующая моя работа была посвящена упрощению доказательства результата Шютценберже о характеризации моноидов без нетривиальных подгрупп. Далее я занялся контекстно-свободными грамматиками и доказал эффективную (алгоритическую) отделимость двух инвариантных свойств (типа линейности и нелинейности) таких грамматик. Известно следующее странное свойство общее теории алгоритмов. Начиная строить эту теорию, мы должны дать некоторое формальное определение понятия алгоритма (скажем, определить машины Тьюринга), но в дальнейшем это определение практически не используется. Я предложил новое машинно-независимое построение теории алгоритмов, основанное на игровом подходе. Кроме того, формальное определение теории алгоритмов позволяет сформулировать и доказать результаты о невозможности (скажем, о невозможности устранения аддитивной константы в определении сложности конечных объектов по Колмогорову -- Соломонову). Следующая моя работа связана с упомянутой в предыдущем абзаце колмогоровской сложностью. Я дал верхние и нижние оценки для возможности выделения общей информации в двух конечных объектах в виде третьего конечного объекта. Клеточные автоматы (? iterative arrays) позволяют рассматривать универсальные в сильном смысле алгоритмы, в которых моделируемые алгоритмы работают параллельно. Я изучил, как это отражается на времени их работы. В 1948 году Тарский сформулировал вопрос: является ли понятие определимости в некотором языке определимым в этом самом языке? Для большинства языков ответ отрицательный; в некоторых случаях возникает независимое утверждение. Я доказал первый нетривиальный положительный результат такого рода (об арифметике Пресбургера). В последнее время одной из моих главных тем была алгоритмическая теория вероятности. Она проливает свет на понятие случайности (которое при классической интерпретации приводит к различным парадоксам). В статье Колмогорова (опубликованной в русском журнале ``Проблемы передачи информации'', 1969, том~5, номер~3, с.~3--7) рассматриваются связи между частотным и алгоритмическими подходами. Мой результат, связанный с этими вопросами, опубликован в русском журнала ``Успехи математических наук'', 1990, том.~45, номер~1, с.~151--154 (он опровергает гипотезу Колмогорова, высказанную в цитированной статье). [конец перевода] [следующий текст написан в конце 199* для какого-то отчета? пе- ред диссертацией?] Список научных трудов Андрея Альбертовича Мучника. 1. О теореме Шютценберже, касающейся моноидов без нетривиальных подгрупп. 1983. Упрощение доказательства. 2. Игры на бесконечных деревьях и автоматы с тупиками. Новое доказательство разрешимости монадической теории двух следований. 1985. Придумано в 1979. В отличие от доказательства Рабина не используется трансфинитная индукция. Games on Infinite Trees and Automata with Dead-Ends. A New Proof for the Decidability of the Monadic Second Order Theory of Two Successors. 1992. Перевод. Гуревич и Харрингтон - 1982. Устранение их пробелов: Яхнис и Яхнис - 1994. Неопубликовано: древесная надстройка структуры - конечные последовательности элементов структуры, отношения надстройки - {1} отношения структуры на последних элементах братьев и {2} равенство последних элементов отца и сына. (Добавление отношения равенства несоседних элементов последовательности делает монадическую теорию древесной надстройки натурального ряда со штрихом неразрешимой, в то время как монадическая теория самой структуры натурального ряда со штрихом, как известно, разрешима.) Теорема: монадическая теория древесной надстройки сводится к монадической теории самой структуры. Шелах и Ступп доказали то же для древесных структур без отношения {2}, что существенно обедняет язык. 3. Применение метода Семёнова к анализу структуры контекстно-свободных языков. 1985. Одно применение действительно-значной интерпретации грамматических рядов. Препринт. 1991. Алгоритмическое отделение линейных языков от сильно нелинейных языков(языков, а не грамматик!). 4. Об основных структурах дескриптивной теории алгоритмов. 1985. Игровая интерпретация теории алгоритмов и релятивизуемые утверждения. 5. Я участвовал в обсуждении проблемы неарифметичности предикатной логики доказуемости. 6. On the extraction of common information of two words. 1986. On common information. 1998. Два метода построения пар объектов с невыделяемой общей информацией. (совместно с А.Е.Ромащенко, А.Х.Шенем, Н.К.Верещагиным) Upper semi-lattice of binary strings with the relation "x is simple conditional to y". 1999. Разные геометрические примеры, метод случайного блуждания по графам. Предстоит опубликовать: самый сильный пример, метод вероятностного построения функций со специальными свойствами. 7. Нижние пределы частот в вычислимых последовательностях и релятивизованная априорная вероятность. 1987. Н.К.Верещагин доказал, что верхний предел условной энтропии (при условии, стремемящемся к бесконечности) равен энтропии с оракулом 0'. 1999. 8. Об одном классе полиномиальных систем уравнений, вытекающих из формулы полной вероятности, и возможности устранения перебора при их решении. 1987. 9. О сильно универсальных сетях конечных автоматов. 1988. 10. On the inclusion of the class BPP into the class П_2. 1991. Упрощение результата Гача. 11.(совместно с С.Ф. Сопруновым) Decidability of monadic theories of countable structures and of their classes. 1991. Существует одноместный предикат на двоичном дереве, который имеет разрешимую слабо-монадическую теорию, но неразрешимую монадическую теорию (в языке с операциями следования). Наоборот не бывает, так как конечность выразима в монадической теории двоичного дерева. Из детерминизуемости автоматов на сверхсловах следует, что монадическая теория одноместного предиката на натуральном ряде со штрихом сводится к слабо-монадической теории. 12. Выразимый критерий выразимости в арифметике Пресбургера и его применения. Препринт. 1991. Вопрос о существовании "самовыразимого" языка поставлен Тарским в 1948. Было известно, что класс одноместных предикатов, выразимых в неразрешимой элементарной теории сложения и умножения натуральных чисел, не выразим в этой теории. Я доказал, что для каждого n класс n-местных предикатов, выразимых в разрешимой элементарной теории сложения натуральных чисел, выразим в этой теории (построение эффективно по n). В другой разрешимой теории сложения и умножения алгебраических чисел класс выразимых одноместных предикатов выразим, а класс выразимых двуместных предикатов не выразим. Выразимость выразимости в арифметике сложения позволила существенно упростить доказательства следующих двух теорем Семёнова. Хорошо известно, что множества n-ок натуральных чисел, выразимые в арифметике сложения, распознаются конечным автоматом при записи в p-ичной системе счисления для p>1 (автомат строится эффективно по арифметической формуле, n и p). Семёнов доказал, что по автомату, распознающему множество n-ок натуральных чисел в p-ичной системе счисления, можно узнать, выразимо ли это множество в арифметике сложения (в случае выразимости формула строится эффективно). Если (log p)/(log q) - иррационально, то множества n-ок натуральных чисел, автоматно распознаваемые при записи и в p-ичной и в q-ичной системах счисления, выразимы в арифметике сложения. 13. (совместно с Н.К. Верещагиным) A general method to construct oracles realizing given relationships between complexity classes. 1994. 14. (совместно с А.Л.Семёновым и В.А.Успенским) Mathematical metaphysics of randomness. 1998. Сравнение сложностного, игрового и частотного подходов к определению случайности бесконечной двоичной последовательности. Колмогоров доказал, что для монотонных правил выбора существует последовательность с логарифмическим ростом сложности начал, в которой при каждом вычислимом правиле выбора частота обеих цифр стремится к 1/2. То же самое без доказательства утверждается в публикации Колмогорова для немонотонных правил выбора. Эта гипотеза опровергнута. Рассмотрение мер, медленно стремящихся к равномерной, показывает, что частотный подход всё-таки не эквивалентен сложностному. Мы даём анализ игрового подхода, который гораздо ближе к сложностному, чем частотный. Впрочем, проблема эквивалентности игрового подхода сложностному остаётся открытой (Ли и Витаньи интересовались в 1999, не решена ли она). Исследуется вопрос о существовании универсальных выигрывающих стратегий. Аналоги основных понятий статьи изучаются для конечных последовательностей. 15. (совместно с С.Е.Посицельским) Об одном классе перечислимых множеств. 1999. Доказано, что r-отделимые множества образуют решётку и что все r-отделимые множества не полны относительно ограниченной сводимости по Тьюрингу. В частности, неполнота простых множеств Поста имеет место при ограниченном количестве обращений к оракулу даже без требования одновременности этих обращений (это требование есть для табличной сводимости). [далее почему-то следует список работ Горбунова, написанный Мучником] Список научных трудов Горбунова Константина Юрьевича. 1. Об одной алгоритмической проблеме математической лингвистики. Тезисы. 1988. Не существует перечислимого семейства контекстно-свободных грамматик, порождающего класс однозначных языков. 1991. Решение проблемы, поставленной в моей работе из [3]. 2. Контекстно-свободная выводимость графов, не реализующих плоскую решётку. 1991. (совместно с R.Diestel, T.Jensen, C.Thomassen) Highly connected sets and the excluded grid theorem. 1999. Основной результат состоит в оценке древесной ширины графа через размер квадратной решётки, которую граф не реализует. Горбунов получил экспоненциальную верхнюю оценку (известная оценка была неэлементарной, нижняя оценка неизвестна) и линейную верхнюю оценку для плоских графов (известная оценка была квадратичной). Работа начиналась с обобщения метода Слисенко. Это обобщение опубликовано в 1999 другими (Курсель, Маковсий, Ротикс). 3. On a complexity of the formula ((A or B) implies C). 1998. [далее Андрей пишет о неопубликованных своих работах - видимо, по состоянию на конец 1990-х годов] Предстоит опубликовать. 1. Беннет, Гач, Ли, Витаньи, Цурек доказали, что сложность минимальной программы, переводящей x в y и y в x, равна максимуму сложностей минимальной программы, переводящей x в y, и минимальной программы, переводящей y в x. Горбунов доказал в [3], что сложность минимальной программы, переводящей x в z и y в z, бывает равна сумме сложностей минимальной программы, переводящей x в z, и минимальной программы, переводящей y в z. Но сложность x,y,z в примере Горбунова экспоненциальна относительно сложности минимальных программ. Я доказал, что с точностью до логарифма сложности z сумма может быть заменена на максимум (при этом сложность x,y может быть любой). Причём, минимальная программа, переводящая x в z и y в z, всегда может быть выделена из z. С другой стороны, минимальная программа, одновременно переводящая x в z и y в z, бывает независима от пары минимальных программ, переводящих по- отдельности x в z и y в z. Наоборот, минимальная программа, одновременно переводящая x в y и y в x, всегда имеет большую общую информацию с парой минимальных программ по-отдельности переводящих x в y и y в x. Дана точная оценка на мощность универсального множества кодов для получения одного объекта из разных условий. [опубликовано сначала в совместной заметке с Семеновым в ECCC, потом в TCS] 2. (совместно с М.В.Вьюгиным) Полное решение следующей проблемы. Для каких чисел a,b выполнено, что каждому объекту x можно сопоставить такой объект y, чтобы было K(x|y)=a, K(y|x)=b? Если ab, то y существует не для каждого x. [видимо, до сих пор не опубликовано] 3. Хорошо известно, что надграфик функции энтропии всегда является слабо- таблично полным множеством. Куммер доказал, что надграфик простой энтропии всегда является таблично полным. Мы с С.Е.Посицельским доказали, что надграфики префиксной энтропии бывают и полными и неполными относительно табличной сводимости. Я доказал, что надграфик условной энтропии всегда является m-полным. Надграфики функций простой и префиксной энтропии однозначно задают две несравнимые перечислимые степени относительно ограниченной сводимости по Тьюрингу (то же выполнено для ограниченной слабо-табличной сводимости). Это первый естественный пример промежуточной перечислимой степени. Для ограниченной табличной сводимости надграфики простой энтропии бывают несранимы друг с другом, и надграфики префиксной энтропии бывают несранимы друг с другом. [видимо, это опубликовано в статье с Посицельским (TCS, до этого анонс в Успехах, сюда же относятся два анонса на конференциях] 4. Одномерная почти-периодичность. (Удобнее определение допускающее "предпериоды".) Детерминированный конечный преобразователь (автомат, заменяющий буквы на любые слова) переводит почти-периодическую последовательность в почти-периодическую последовательность. При этом сохраняется эффективность задания. Недетерминированный преобразователь можно униформизовать недетерминированным преобразователем, который эффективно находится. Недетерминированный преобразователь, получающий на вход почти- периодическую последовательность, можно униформизовать детерминированным преобразователем, который эффективно находится (и зависит от входа). Если входная последовательность не почти-периодична, то детерминированная униформизация бывает невозможна. Универсальный метод построения почти-периодических последовательностей. Важные примеры почти-периодических последовательностей в топологических и метрических компактах, на многомерном торе. (Эффективная) почти-периодичность многомерной последовательности не следует из (эффективной) почти-периодичности всех её собственных проекций. У почти-периодической последовательности начало длины n имеет дефект случайности больше cn для подходящей костанты c. Для каждой константы c существует почти-периодическая последовательность, у которой дефект случайности n-ого начала меньше cn. [вероятно, по большей части вошло в статью с Семеновым и Ушаковым] 5. Разные оценки для конечных автоматов и преобразователей.