molpit
Login:
Password:
remember
PIT00150 Сложность Колмогорова кляксы и клетки

С благодарностью отвечая на хорошие замечания Кирилла к посту PIT00149, разогнался так, что чуть было не потерял большой текст, который изложен ниже с надеждой получить развёрнутые суждения по существу. Замечания Кирилла показали мне, что принципиальное отличие энтропии Шеннона и сложности Колмогорова надо обсуждать глубоко, т.к. только понятие алгоритмической сложности Колмогорова позволит определить и понять биологическое взаимодействия, кляксу как квантовый образ химического сигнала, самоорганизацию и т.п.

Алгоритмическое определение сложности сделал Колмогоров в 1965 году

https://ru.wikipedia.org/wiki/Колмогоровская_сложность и https://en.wikipedia.org/wiki/Kolmogorov_complexity

Колмогоровская сложность
В алгоритмической теории информации колмогоровская сложность объекта (такого, как текст, клякса, клетка) есть мера вычислительных ресурсов, необходимых для точного определения этого объекта (внешним наблюдателем). Когда весь вычислительный ресурс находится в другой кляксе (клетке), то именно колмогоровская сложность естественно связать с преобразованием одной кляксы в другую, и попытаться вычислить размерные характеристики преобразования (вычисления, измерения).
Колмогоровская сложность также известна как описательная сложность, сложность Колмогорова — Хайтина, стохастическая сложность, алгоритмическая энтропия или алгоритмическая сложность.
Выражает возможность фрактального описания (см ссылки на Wiki выше).

Определение
Чтобы определить колмогоровскую сложность, мы должны сначала задать язык описания строк. Такой язык описания может быть основан на любом языке программирования, таком как Lisp, Pascal или Java-байт-код. Если P — программа, выходом которой является строка x, то P — описание x. Длиной описания является длина P как строки. В ходе определения длины P длины подпрограмм, использующихся в P, должны быть вычислены. Длина любой целой константы n, которая появляется в P, это количество бит, требующихся для представления n, равное (грубо) log2n. Белобров делал попытки определить колмогоровскую сложность в теории самоорганизации биологических систем начиная примерно с 1968 года (детали в докт. диссертации). Модель Денисова, особенно в её новой постановке для самоорганизации многомерных клякс, позволит решить проблему либо существенно уточнить её формулировку.

История и контекст
Алгоритмическая теория информации — это области компьютерной науки, изучающая колмогоровскую сложность и другие сложные меры для строк (или других структур данных). (Точные детали см. в Вики статье и в рукописи нашей полной статьи, которая готовится к опубликованию). Обсуждение алгоритмической и содержательной теории биологической информации сделано в диссертации Белоброва, где было показано, почему определение Шеннона для энтропии недостаточно для описания биологических процессов в пространстве структур и функций. Немного есть в статье Зимина и К (дек. 2013, Валеология) в цитируемой там работе [Антомонов, Белобров. Энтропия живых систем // Энциклопедия кибернетики, 1974]

Основные следствия
В последующих рассуждениях под K(s) будем подразумевать сложность кляксы (клетки) s. Несложно заметить, что минимальное описание кляксы не может быть больше, чем сама клякса. Добавлю, что понятия больше и меньше также надо определять. Скорее всего сравнение надо будет делать по биологической мере.

Невычислимость колмогоровской сложности
Первое следствие заключается в том, что нет эффективного способа вычисления K.
Теорема. K — невычислимая функция.
Другими словами, не существует программы, которая бы принимала на вход кляксу s и выдавала бы на выходе целое число K(s). Покажем это с помощью противоречия путём создания программы, которая создает кляксу, создать которую возможно только более длинной программой. В биологических вычислениях (измерениях) в отличие от исчисления в компьютерных программах возможно даже будет справедлива обратная
Теорема. K — вычислимая функция!!!
Предположим, что существует биологическая программа преобразования клеток и клякс, которую мы написали в CellBook. Кляксовые и клеточные "вычисления" и будут скорее всего измерениями по биологической мере, позволяющими вычислить колмогоровкую сложность клетки.

Цепное правило для колмогоровской сложности
Цепное правило для колмогоровской сложности утверждает, что
K(X,Y)=K(X)+K(Y∣X)+O(logK(X,Y)).
Оно утверждает, что кратчайшая программа, воспроизводящая X и Y не больше чем на logK(X,Y) превосходит по размеру программу, воспроизводящую X, и программу, воспроизводящую Y при данном X. С использованием этого выражения можно определить аналог взаимной информации для колмогоровской сложности.

Сжатие кляксы и клетки
Вычислять верхнюю границу для K(s) несложно: нужно просто сжать кляксу s каким-либо методом, реализовать соответствующий декомпрессор на выбранном биологическом языке, соединить декомпрессор со сжатой кляксой и измерить длину полученной кляксы (клетки). Клетки это умеют делать по биологическим мерам, когда одна клетка измеряет другую клетку. В принципе это можно делать в модели Денисова (хотя мы не пробовали пока). См. детали в тексте статьи, которая пишется.

Теорема Белоброва-Зимина о неполноте (первый анонс)
Известно, что во множестве всех возможных клеток большинство клеток являются сложными в том смысле, что не могут быть описаны в любом достаточно сжатом виде. Однако, оказывается, что тот факт, что конкретная клетка сложна, не может быть формально доказан, если сложность клетки выше определённого порога.

Колмогоровская случайность клетки
Согласно определению колмогоровской случайности (тж. алгоритмической случайности) строка называется случайной тогда и только тогда, когда она короче любой компьютерной программы, способной её воспроизвести. Чтобы сделать это определение точным, нужно зафиксировать универсальный компьютер (или универсальную машину Тьюринга), так что "компьютерная программа" будет обозначать программу для этой универсальной машины. Клетка называется случайной тогда и только тогда, когда она короче любой биологической программы, способной её воспроизвести.
Минимальная длина биологического сообщения
Принцип минимальной длины биологического сообщения нигде и никем пока не разработан! Но понятно, что передача биологической информации (например, везикулами между клетками) может быть как разной сложности и разной оптимальности.

Основная литература с небольшими комментариями "по делу"

[blot01] [62] Колмогоров А. Н., Три подхода к определению понятия «количество информации» Kolmogorov1965r (pdf, 964КБ) // Проблемы передачи информации, т. 1 (1965), вып. 1, с. 3-11. Английский перевод: Kolmogorov A. N., Three approaches to the quantitative definition of information Kolmogorov1965 (pdf, 585КБ) // Problems Inform. Transmission, v. 1 (1965), no. 1, p. 1-7. На англ. статью сослались 2245 раз (на русскую статью всего 291 раз)!!!

[blot02] [63] Колмогоров А. Н., К логическим основам теории информации и теории вероятностей (нашёл, завтра положу сюда) // Проблемы передачи информации, т. 5 (1969), вып. 3, с. 3-7. Несколько раньше опубликован английский перевод (переводчик не указан) Kolmogorov A. N., Logical basis for information theory and probability theory // IEEE Trans. Inform. Theory, v. 14 (1968), p. 662-664.

[blot03] А. К. Звонкин, Л. А. Левин. Сложность конечных объектов и обоснование понятий информации и случайности с помощью теории алгоритмов Zvonkin1970 (pdf, 4899КБ) // УМН, 25 (6), 85-127 (1970). Мы встречались с Сашей Звонкиным (зима 1969-1970), и он подробно в лицах рассказывал то, что написано в начале этой статьи (это диссертация Саши) и многое другое. Мы с ним гуляли по Москве... узнал я как Андрей Николаевич Колмогоров послал Шеннона туда, куда Масяня директора посылала, когда ректор МГУ Петровский просил А.Н. встретить великого человека, который приезжал в МГУ, но А.Н. был занят! Сейчас Саша учит детишек Zvonkin2006 (pdf, 4203КБ) Звонкин А. К. Малыши и математика. Домашний кружок для дошкольников. 2006. 240 с., а его шеф Лёня Левин продолжает в Бостоне http://www.cs.bu.edu/~lnd/ "грызть гранит" вычислительной сложности. Лёня независимо от Стивена Кука доказал в 1971 году теорему Кука — Левина, благодаря которой была сформулирована проблема равенства классов P и NP, ставшая одной из задач тысячелетия. Работа была опубликована только в 1973 году, но была доложена на конференциях, что позже позволило установить приоритет Левина.

[blot04] Верещагин Н. К., Успенский В. А., Шень А. Vereshchagin2012 (pdf, 3839КБ) Колмогоровская сложность и алгоритмическая случайность. М. МЦНМО, 2012. 588 с. Классическая (шенноновская) теория информации измеряет количество информации, заключённой в случайных величинах. В середине 1960-х годов А. Н. Колмогоров (и другие авторы) предложили измерять количество информации в конечных объектах с помощью теории алгоритмов, определив сложность объекта как минимальную длину программы, порождающей этот объект. Это определение послужило основой для алгоритмической теории информации, а также для алгоритмической теории вероятностей: объект считается случайным, если его сложность близка к максимальной.
Предлагаемая книга содержит подробное изложение основных понятий алгоритмической теории информации и теории вероятностей, а также наиболее важных работ, выполненных в рамках «колмогоровского семинара по сложности определений и сложности вычислений», основанного А.Н. Колмогоровым в начале 1980-х годов.
Книга рассчитана на студентов и аспирантов математических факультетов и факультетов теоретической информатики. Да и квантовым химикам она явно не повредит! Не верите? Тогда вперёд на стр.522 и читайте "Ещё одно отступление: квантовая механика". Книгу рекомендую как лучшую по колмогоровской сложности и очень грамотную.

[blot05] Б.Я. Рябко. Бесшумное кодирование комбинаторных источников, хаусдорфова размерность и колмогоровская сложность Ryabko1986 (pdf, 1394КБ) // Пробл. передачи информ. 22 (3), 16–26 (1986). Я полста лет развиваю теорию процесса включения и выключения взаимодействия, при котором изменяется размерность, применяя меру Хаусдорфа. Подробнее всего это изложено в моей диссертации https://molpit.org/page/36, но не было опубликовано!

[blot06] Вьюгин, В. В. Vyugin2012 (pdf, 805КБ) Колмогоровская сложность и алгоритмическая случайность. М. ИППИ РАН (2012). 140 с.

Следующие ссылки относятся к очень близким к нам объектам и процессам.

[blot07] Иваницкий Г. Р., Медвинский А. Б., Цыганов М. А. От динамики популяционных автоволн, формируемых живыми клетками, к нейроинформатике Ivanitskii1994 (pdf, 793КБ) // УФН 164 1041–1072 (1994). Аннотация. Живые клетки и их сообщества представляют собой объект исследования, с помощью которого можно пытаться подойти к решению достаточно общих проблем: каковы алгоритмы обработки информации в живых системах? В чем отличие живых «компьютеров» от их технических аналогов? Показано, что техническая реализация поведения «клетки», обладающей подвижностью, памятью и таксисом и способной размножаться, может дать существенный выигрыш во времени при анализе изображений по сравнению с телевизионными автоматами. Исследования динамики популяционных автоволн, формируемых живыми клетками, представляют особый интерес для физики автоволн, поскольку популяционные автоволны существенно отличаются от «классических волн» в активных средах. В математических моделях специфика популяционных автоволн проявляется как дополнительный член, описывающий не беспорядочное, а направленное движение отдельных клеток ("эффект хемотаксиса’). Подробный анализ таких моделей и описываемых ими феноменов (например, образование статических структур при взаимодействии популяционных автоволн, а также нарушение симметрии образуемых ими волновых картин) может явиться целью будущих исследований. Ссылки 7 и 8 на Колмогорова, 1965

[blot08] Иваницкий Г Р, Медвинский А Б, Деев А А, Цыганов М А "От "демона Максвелла" к самоорганизации процессов массопереноса в живых системах Ivanitskii1998 (pdf, 519КБ) // УФН 168 (11), 1221–1233 (1998). Аннотация. При циклическом взаимодействии «микрочастицы \leftrightarrow среда» часто возникает направленное стохастико-детерминированное движение микрочастиц. Из перемещающихся микрочастиц образуются динамические структуры. Обзор посвящен анализу возникновения направленного движения микрочастиц при наличии слабых управляющих асимметричных периодических полей. Приведена энергетическая оценка минимальной стоимости преобразования случайного движения в направленное. Обсуждается приложение этих результатов к описанию регуляторных процессов в биосистемах: при взаимодействии движущихся хемотаксисных бактерий и бактериальных вирусов, мышечном сокращении, при движении везикул, ферментов и ионов внутри живых клеток. Рассматриваются некоторые приложения этих явлений в наукоемких технологиях. Ссылки 89 и 90 на Колмогорова, 1965

[blot09] Михайловский Г.Е. Организация времени в биологических системах // Журн. общ. биол 50 (1), 72-81 (1989). Взять в б-ке ИБФ СО РАН и сделать скан! А пока только Аннотация (перевод с английского!)
Введено понятие организации времени, аналогичное понятию организации пространства в архитектуре системы. Уровень и структура организации времени в биологических системах отличается от таковой в физических и химических системах, что представляет независимое проблему. Анализ проблемы приводит к новому определению жизни как процесса перенормировки возможностей, описанных формулой Байеса. Это определение приводит к понятию самоконтроля как свойство любой биологической системы, а также сложной структуры биологического настоящего, включающее физическое прошлое и физическое будущее. Это, естественно, ведёт к последующим определениям далекого прошлого, и, следовательно, к памяти и определению будущего, то есть пред-адаптация, исключительная рефлексия, установление цели и т.д. Была показана прямая зависимость числа элементов сложной системы на её устойчивость. Самоконтроль и организацию времени можно проследить на различных уровнях биологической иерархии от внутриклеточного до биосферного уровней.

Peter Belobrov 26 Oct 2014 11:14
© International Open Laboratory for Advanced Science and Technology — MOLPIT, 2009–2022