Z-talk с нуля

Я так часто переписывал Z-talk с нуля, что у меня самого появилось чувство, что я его никогда не допишу. Пора остановиться и довести до рабочего состояния то, что уже есть.

План такой: я буду писать раз в неделю пост о своем прогрессе. Сегодня первый пост из этой серии.

В основе, Z-talk — это лисп. Наиболее близкий диалект — Scheme. Фундаментальное отличие в поддержке макросов в стиле Common Lisp.

Реализация начинается с простейшего интерпретатора, который я пишу на C++.

Сначала я реализую простейший сборщик мусора. Mark&sweep с интерфейсом, состоящем из функций: add_root(), del_root() и собственно gc().

Дальше поддержка примитивных типов данных. Вот базовый набор: fixnum, bignum, char, string, symbol, bool, none, nil, pair, vector, а также файловые и строковые порты ввода-вывода.

Реализация классическая — fixnum, char, bool, none и nil представлены в виде машинного слова, два последние бита которого представляют собой тег (один бит для fixnum). Если тег равен нулю, то слово интерпретируется как указатель на объект в куче. Каждый такой объект имеет заголовок из нескольких битовых полей: несколько бит, использующихся сборщиком мусора и id типа. Id типа — это индекс в глобальной таблице типов. Каждый элемент этой таблицы — запись, включающая информацию о размере объекта в байтах, имя, используемое в целях отладки, битовый массив, определяющий какие машинные слова в объекте могут быть указателями (используется для фазы mark сборщика мусора), а также набор указателей на функции: hash, equal, destroy, print, dump.

Для типов, встроенных в машинное слово, кроме fixnum (назовем их immediate), id типа закодировано в битах со 2 по 7.

Реализацию я начинаю со списка unit-тестов, которые почти исключительно представляют собой список акимом для базового набора типов.

Для типов fixnum/bignum — это обычная арифметика. Для symbols — это операций преобразования из строки и обратно, а также проверка на идентичность копий. Для pair — это классические cons, car, cdr.

Продолжение следует.

Чего не хватает Европе

На мой взгляд, европейская цивилизация по многим параметрам круче всего остального мира. Жить лучше всего именно тут. Лучше в широком смыле -- лучше работать, отдыхать, растить детей и пр.

Конечно же, Европа -- это много очень разных стран. И жизнь, скажем, в Польше совсем не такая, как в Нидерландах. В этом контексте я имею в виду саму развитую Европу: Нидерланды, Данию, Бельгию, Люксембург, Швейцарию, Норвегию. Можно в этот список, наверное добавить и Францию с Германией, но где-то нужно все-таки остановиться.

США (опять же на мой взгляд) далеки от северной Европы по уровню общественной зрелости. И хоть по отдельным параметрам некоторые штаты даже круче, я все равно предпочитаю Европу.

Мой любимый Сингапур за последние два года (которые я живу в Нидерландах) в моем личном рейтинге стран упал значительно. У меня по-прежнему к нему сохранились романтические чувства, но из топ-5 он, пожалуй, выбыл.

Вообще-то, когда начинаешь делать подобного рода обобщения, то неизбежно находишь сотни исключений и оговорок. Нельзя просто так сказать, что в Нидерландах жить лучше, чем, например, во Франции. И не только потому, что каждому свое (это-то очевидно), а потому что я даже для самого себя не могу точно определить, что важнее: комфортная жизнь или культура, носителями которой являются жители страны. Такие вещи стравнивать очень сложно, потому что комфорт очень сильно зависит от наличия культурного наследия. То есть сегодня мне самым важным кажется то, что люди на улицах Харлема очень сдержаны, добры, приветлевы и искренни, а завтра я прочитаю афишу кинотеатра и пойму, что там нет ни одного стоящего фильма, снятого нидерландским режисером. Или даже чисто в отношении комфорта: с одной стороны одним из самых важных аспектов жизни для меня является наличие комфортных общественных пространств в непосредтсвенной доступности. Я люблю жить среди людей. Никакой трехэтажный дом с машиной, яхтой и не важно чем еще где-нибудь далеко за городом мне не нужен, если до ближайшего кафе нельзя дойти пешком. Или даже если это кафе близко, но его с трех сторон окружают широкие шумные дороги, а с четвертой гиганская парковка. Но с другой стороны, легко придумать экстемальный пример: если вы живете в очень маленькой квартире в старом доме со старой сантехникой, где шумит водопровод, а туалет чуть ли не на веранде, то в каком бы центре он не находился, как бы ни были уютны улицы вокруг вашего дома, рано или поздно вам захочется перемен. Захочется иметь место, куда бы можно было ставить мотоцикл, захочется чистую теплую просторную ванную комнату, в которую влазит что-то еще кроме стиральной машинки и раковины и душевой кабинки.

Таким образом, я не могу совершенно однозначно определиться, где именно жить лучше всего. Даже для самом себя. На данные момент, как я уже сказал, это северная Европа. Нидерланды, пожалуй, на первом месте, а дальше по списку, который я привел выше.

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

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

Каждый раз когда поднимается тема иммиграции, все обсуждают любый вопросы, кроме самого важного: когда же наконец иммигранты, выходцы из мусульманских стран, принесут в Европу традицию организовывать туалеты так, чтобы в них всегда был доступ к водопроводной воде?

Про Францию

Недавно к Тане приезжали родители и мы с ними съездили во Францию. Для меня это был уже второй раз, но раньше мы были только в Париже, а на этот раз сняли машину и прокатились еще по Нормандии. Заехали в Этрету (Étretat) и Трувиль-сюр-Мер (Trouville-sur-Merу).

Еще от прошлой поездки у меня осталось очень положительное впечатление от Парижа. Оно было особенно ярким от того, что ожидания были самые худшие. Раньше я о Париже слышал почти только плохое. А оказалось, что город очень обаятельный. Причем многое из того, что говорили оказалось правдой, но только не такой значительной. А положительные вещи оставили гораздо более яркий след. То есть, скажем, пробки и большое количество машин -- правда, но движение не очень сильное, не очень шумное, везде есть тротуары, а пешеходные переходы всегда наземные и огранизованы достаточно удобно. Местами грязновато и даже (как мне верно говорили) иногда пахнет туалетом, но это скорее исключения и общее впечатление от этого не испортилось. Французская надменность и нежелание знать никакой другой язык, кроме французского, преувеличены. То есть английский и правда знают очень немногие, но все всегда готовы тебя слушать, пытаются понять как могут и погают. Это даже немного приятно, особенно после двух лет в Нидерландах, где все мгновенно переключаются на английский, стоит им понять, что ты иностранец, даже если ты искрене пытаешься связать пару слов на их языке. На улицах всегда есть жизнь. Люди заняты самыми разыми вещами. Даже просто так ходить и наблюдать за жизнью города очень интересно. Даже более интересно, чем, скажем, в Амстердаме. В Нидерландских городах обычно намного уютнее и комфортнее, да, пожалуй, и красивее. Но если судить по тому, чем заняты люди на улицах, то Париж выигрывает. Люди собираются в группы, на чем-то или во что-то игают, что-то читают, бегают, катаются на досках и прочее.  Все это есть и тут в Нидерландах, но в основном по праздникам или в выходные, когда проходят какие-нибудь фестивали. А Париже все это как-то спонтанно и поэтому более жизненно и интересно.

Но на этот раз я был в Париже совсем чуть-чуть (Таня была в отпуске и она с родителями приехала раньше и осталась подольше, а я только на выходные прилетал), в основном мы время провели в Нормандии -- как я уже написал, в двух городах на море, а ночевали в Грюше-ле-Валасе (Gruchet-le-Valasse).

И вот тут согласно стереотипам мне Франция должна была бы понравиться  еще больше. А оказалось наоборот. Но я не собираюсь никого ни в чем убеждать -- каждому свое. Просто меня обычно очень мало интересует природа как таковая и я гораздо больше обращаю внимание на то, как организавана жизнь людей даже если речь идет об очень маленьких городах или деревнях. По этому параметру, конечно, я не знаю ни одной страны, которая хоть немного бы приблизилась к Нидерланам. А так как за последнее время в моем мозгу "ноль выставился" именно на Нидерланды, то я совершенно не могу хорошо относиться ни к какой другой стране. Ну, ладно, преувеличиваю -- в Дании вроде все нормально и, возможно в Швеции (я совсем чуть-чуть там был). Так вот Франция после этого кажется хаосом. Что, понятное дело, неправда -- стоит вспомнить как дела обстоят во Вьетнаме, в Индонезии или на Филиппинах (да и в России, чего уж там) и все встанет на свои места.

Еще одна одна причина, почему мне вне Парижа не очень понравилось в том, что мы были в самых туристических местах, а это всегда портит впечатление от поездки. Плюс ко всему, у меня давно выработалось отвращение ко всем морским курортам. Я не люблю пляжные атрибуты и иногда даже кажется само море. Самый терпимый вариант для меня -- это пустой холодный ветряный пляж -- купаться я все равно не люблю (разве что немного в речках и озерах), а так хоть красиво и без голых отвратительных тел. В этом смысле какой-нибудь Зандфорт или Гаага -- норма, а еще лучше где-нибудь в Ирландии.

Как бы то ни было, в целом впечатления остались замечательные. Обязательно поедем во Францию еще. И не раз.


Есть вещи, к которым я никогда не привыкну

Независимо от того, насколько долго я пользуюсь всякими Endomod'ами, Strav'ами и Runkeeper'ами,  я никогда не привыкну к тому, что они называют скоростью то, что на самом деле является "медленностью".

Speed, pace или tempo -- все это не может измеряться в минутах на километр. 6 мин/км -- это не скорость и не темп. 8 мин/км больше чем 6 мин/км, при этом скорость или темп, соответствующие 8 мин/км -- меньше.

Это все равно что радиус кривизны путать с кривизной. Если радиус больше, то кривизна -- меньше. Если сопротивление больше, то проводимость -- меньше. И дело не в единицах измерения. Нельзя изменять проводимость в Омах, а кривизну в метрах.

Особенно забавно, когда разработчики приложения чусвтуют подвох и вместо Speed пишут Pace (темп) или Tempo (тоже темп). На это грустно смотреть. Ведь это ровным счетом ничего не меняет. Больший темп -- это меньше мин на километр. Называть эту величину любым синонимом скорости -- это такая же глупость, как и называть ее скоростью.

Если вам так важно записывать этот показатель в мин/км, то придумайте для этой величины адекватное название. По смыслу это должно быть синонимом медленности: тормознутость. Вот правильно же звучит: ваша тормознутость 8 мин/км. А теперь ваша тормознутость -- 6 мин/км. Все логично. Ваша тормознуость упала на 2 мин/км. Не скорость упала, и не темп. Скорость и темп как раз выросли.

Помню, когда я жил в Малайзии и перед покупкой мотоцикла читал малайские форумы, я часто встречал, что люди жаловались на потребление топлива (consumption), при этом писали величины в км на литр. Тогда я был уверен, что это потому что в Малайзии никто вообще не знает элементарную физику. Я как раз там преподавал физику и не было дня, когда я бы не ужаснулся от их образования. Читая форумы, я лишь видел в этом подтверждение моих представлениях об их образовании. Особенно глупо то, что для величины, измеряемой в км/л есть отличное название -- экономичность.

И вот теперь, когда я почти каждый день вижу все эти мин/км, у меня уже нет возможности объяснить это хреновым Малайзийским образованием.

Куда катится этот мир?

Плов с вешенками как у Сталика

Сто лет не заглядывал во френд-ленту ЖЖ. А тут решил почитать, а там -- Сталик со своими супер зажигающими постами. Все те несколько случаев в жизни, когда я готовил ради удовольствия, а не из необходимости, происходили именно благодаря Сталику. И дело не только в том, что фотографии у него супер-крутые (а они супер-крутые), а еще и в том, что описывает он приготовление так, что хочется прям бросить свою професси и все жизнь посвятить готовке. Я помню даже сыр делал домашний еще когда в общаге МАИ жил -- тоже после одного из его постов.

Так вот на этот раз -- плов с вешенками. Для его приготовления у меня не было ничего вообще. Но мы же живем в 21 веке -- пробежался с утра по магазинам и вот тебе и некоторое подобие казана (со скидкой 50% -- большая удача), и вешенки свежие из Albert Heijn'а, и два вида перца и вяленые помидоры. Про морковку, лук, честнок, кориандр, морковь и говорить не стоит -- все это можно купить где-угодно.

Прогулялся по Большой деревянной, свернул на Гостинную набережную -- и через час всё необходимое было дома:

Приступаем. Режем лук, честнок, перцы и морковь.

Зажариваем на сильном огне лук и честнок.


Параллельно отвариваем вешенки.

Не забываем солить. Добавляем оставшиеся овощи.

Когда вешенки готовы, ставим рис (лучше было это делать заранее, и так все получилось неплохо).

Последним делом закидываем вяленые помидоры. Ах да, чуть не забыл -- перед помидорами еще ложку сахара нужно было.

Перед закидыванием риса все это выглядело так:

Теперь сверху высыпаем только что отброшенный на дуршлак рис и ставим все в разогретую до 130 градусов духовку.

Теперь есть час свободного времени, чтобы выложить фотки, написать пост и пригласить друзей на ужин.

Так... уже пол часа осталось. Насколько вкусно получилось напишу отдельно в следующем посте через часик.


Почитайте вот, как это было у Сталика.


Интересное наблюдение о ФС HAMMER

Я использую DragonFly BSD. У себя на десктопе и на своем личном сервере. И вот недавно произошло следующее.


Я решил создать бэкап всего своего домашнего хозяйства на удаленном сервере (если что другие бэкапы на всяких облаках mail.ru и прочих дропбоксах у меня есть, но мне приятно когда я полностью контролирую свои данные). А это на минуточку около полутора терабайт всякого хлама.
Разбирать этот хлам времени нет, поэтому я копирую тупо все. Копирую я, естественно не rsync’ом, не cpdup’ом и не какой-нибудь другой модной утилитой, а встроенными средствами файловой системы HAMMER. Для тех, кто не в курсе: HAMMER — это полностью copy-on-write файловая система. То есть абсолютно все состояния файловой системы (с точностью до каджого sync’а) существуют до тех пор, пока не будут явно удалены. Естественно, чистка истории тоже автоматизирована, но если все эти средства выключить, то ни один байт никогда не удалится.

Так вот, что произошло: до установки на свой домашний комп DragonyFly, мои данные лежали на маковской HFS, потом, когда я купил свою первую Raspberry PI, я подсоединил свой дисковый массив к ней, поставил NetBSD и данные переписал на старую добрую UFS. А когда я в последний раз их копировал на HAMMER, то моей последней операцией было переименование корневого каталога, где все эти данные лежали.

Так как, во время копирования, я еще параллельно кое-что чистил (удалял некоторые бэкапы баэкапов) и копировал дополнительно данные с облаков и пр, то в конец перед заливкой этого на удаленный сервер, я удалил всю историю HAMMER’а (hammer prune-everything), чтобы не копировать лишнего.

И вот после этого я обнаружил интересный эффект: так как HAMMER при клонировании файловой системы гарантирует консистентность копии в любой промежуточный момент времени (что само по себе является очень хорошим свойством), я по прошествии суток все еще не увидел на сервере (где я делаю бэкап) ни единого файла. Это происходит как раз из-за того, что одной из последних локальных операций было переименование корневого каталога, а история после этого была стерта. В результате HAMMER не может показать мне консистентое состояние до тех пор, пока не воссоздаст на удаленном сервере всю гигантскую папку в ~1.5ТБ и одной из последних операций не закоммитит создание корневого каталога, ведь старое имя каталога уже не существует в истории.

Вот так я сам себя загнал в ситуацию, где я не смогу иметь доступ ни к одному файлу на удаленном сервере до тех пор, пока не скопируется все вместе.
А стоило мне сделать hammer prune-everything ДО последнего переименования, и я бы смог наблюдать за плавным пополнением бэкапа.

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

Пара в C++

Стандартные (и не очень) контейнеры std::map, std::unordered_map, boost::flatmap и т. п. не должны навязывать пользователю расположение в памяти своих элементов. Вместо этого должны они должны принимать любой тип, удовлетворяющий концепту пары.

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

То же самое должно быть можно сделать и для ассоциативных контейнеров.

Нет никакого фундаментального причины, почему я не могу хранить в std::unordered_map, скажем, 32-битное число, в котором четные биты — это ключ, а нечетные — значение. Если это число — код Мортона, то предоставление такой возможности очень даже имеет смысл. Да и не нужен такой экзотический пример, вот пример проще: у пользователя уже есть стуктура struct Pair { int key; int value; } и он имеет полное моральное право хранить эти структуры в контейнерах STL.

Как это сделать? STL должна определить формальный концепт пары и предоставить пользователю определять специализации метафункций нахождения типов ключа и значения, а также функций доступа к элементам. Вот и все.

Как будет выглядеть определение std::map над вышеупомянутой Pair { int key; int value; }?

namespace std { template<> struct pair_traits<Pair> { typedef int type_of_key; typedef int type_of_value; }; int pair_get_key(const Pair &p) { return p.key; } int pair_get_value(const Pair &p) { return p.value; } }

После этого, должно быть можно пользоваться std::map<Pair>, boost::container::flatmap и всем этим зоопарком.

Замечание, все это я пишу на скорую руку утром в субботу, не проверяя даже, компилируются мои примеры или нет. Я подозреваю, что еще понадобиться определить кое-какие другие специализации, чтобы добиться правильной работы std::make_pair и, возможно, кое-что еще.

Но я думаю, идея ясна.

Что такое неразрешимая проблема

Я не смогу объяснить вам что такое неразрешимая проблема, ни тем более привести пример такой проблемы, без точного определения понятий «проблема» и «решение», поэтому держите сразу же два определения.

Проблема — это множество строк из нулей и единиц.
Решение — это машина Тьюринга, котороая останавливается, какую бы строку ей ни подали на вход, причем останавливается в заранее выбранном состоянии, при условии, что ей подали одну из строк проблемы, и в каком-то другом на всех остальных строках.

Ах, да. Совсем забыл сказать, прочитав этот пост вы не решите ни одну из своих проблем.

А если серьезно, что за странные определения?

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

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

Как закодировать двоичной строкой направленый граф? Ну, например, дать имена вершинам, перечислить их через запятую, а потом выписать дуги в виде пар (пары в скобках через запятую). А дальше все это преобразовать в двоичную строку с помощью ASCII.

Ну а как насчет такой задачи: вычслить значение π.
Тут немного сложнее, потому что определение хорошо подходит для проблем, которые формулируются в виде вопроса с ответом да/нет, а здесь требуется вывести число. Но можно поменять формулировку: найти N-ую цифру двоичной записи числа π. Или даже так: определить, является ли N-ая цифра двоичной записи числа π 1? Ну, вы поняли идею.

Небольшие уточнения: строки конечные, множества строк, в общем случае бесконечные, хоть и счетные, но это неважно для понимания сути.

С проблемами разобрались. А что насчет решений? Машина Тьюринга -- это формальный способ описания алгоритма. Всякие программы на языках програмирования не подходят, потому что для них почти никогда не определена формально семантика. Есть редкие исключения вроде SML, но и там есть свои трудности. Если вы знаете что такое машина Тьюринга, хорошо. Если нет, дальше все равно можно читать, потому что я не буду выписывать МТ формально. Важно только помнить, что одна машина Тьюринга -- это не компьютер, а реализация одного алгоритма, то есть что-то вроде компьютера с единственной программой, зашитой в чип. (Если вы слышали где-то что МТ -- это типа компьютер, то скорее всего имелась в виду универсальная МТ.)

Теперь, собственно, о неразрешимых проблемах.

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

Формулируется она так: определить остановиться ли заданная МТ, если ей подать на вход заданную строку.
Более формально: множество строк, в которых закодированы описания машин Тьюринга и их входных данных, таких, что эта МТ на этих данных рано или поздно останавливается.
Менее формально: по заданному описанию алгоритма и входных данных к нему, определить, остановится он или «зациклится».

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

Существует множество доказательств неразрешимости этой проблемы. Я приведу то, которое нравится мне.

Оно очень короткое и основывается на одном факте, который сам по себе очень интересен. А именно: существует МТ, которая записывает свое собственное описание на ленту. В терминах программ на языках программирования это означает, что на каждом языке (если он не менее мощный, чем МТ) можно написать программу, которая выводит сама себя.

Начнем именно с этого. То есть я попытаюсь вас убедить, что есть такая машина Тьюринга. Самым честным доказательством этого факта было бы полное описание такой машины. Но так как оно чрезвычайно большое, я лучше объясню как его построить.

Итак. Наша МТ будет состоять из двух частей. Назовем их просто A и B.

Машина A будет выводить на ленту описание B.
А машина B будет выводить на ленту описание A.

Все. Факт доказан :-).

Нет, конечно. Это жульничество. То есть на самом деле так оно и будет, но это объяснение ничего не стоит.
Если в лоб попытаться описать машину A (которая пишет описание B), то окажется, очевидно, что она как минимум длиннее B. (Если вам легче мыслить в терминах языков программирования, то программа, которая выводит какую-либо строку, в общем случае, длиннее этой строки.)
Поэтому, даже если часть A можно описать, то с частью B возникает проблема: если использовать тот же способ, то ее размер будет больше A, что приводит к противоречию.

Однако, заметьте, что к моменту, когда A завершила работу, на ленте записано описание B. Теперь всего-то нужно: описать МТ, которая по заданной строке конструирует МТ, которая пишет эту строку. Назовем такую машину B.

А теперь следите за руками: А пишет B, а B пишет то, что пишет B, то есть A.

Если вам все еще кажется, что я вас обманул, вот формулировка в терминах языков программирования: нужно написать программу (B), которая принимает на вход любую строку, а на выход пишет программу, которая выводит эту строку. Если запустить эту программу и передать ей на вход программу B, то она выведет программу A (или ее эквивалент).

Такую программу (B) написать легко и ее размер не зависит ни от чего. Ее вывод зависит от того, какую строку передали на вход, но сама она строится независимо один раз для любых входых данных.

Есть некоторые технические проблемы с тем, чтобы части A и B оказались на выходе в нужном порядке да еще и таким образом, чтобы после отработки части A, МТ переходила в начальное состояние части B, но я не стану тратить время на такие мелочи -- вам придется мне поверить, что они легко решаются :-).

В любом случае, если вам интересна эта тема вне контекста разрешимости, поищите в гугле по слову «квайн». 

И тут мне очень хочется перейти, наконец, к проблеме останова. Но пока не могу. Дело в том, что для доказательства нужна МТ, которая не только выводит себя на ленту, а еще и делает произвольные действия после этого. Но в этом несложно поверить: пробегитесь глазами еще раз описанию, ни что не мешает машине B после своей основной задачи сделать любые другие действия. Сомневающихся я отправляю к книге Майкла Сипсера «Введение в теорию вычислений.»

Ну и наконец, проблема останова.

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

Сконструируем МТ, которая делает следующие шаги по порядку:
1. Записывает себя на ленту.
2. Рядом пишет пустую строку в качестве входых данных.
3. Определяет, остановиться ли записанная на ленту машина на записанных входых данных (то есть, по сути, определяет, остановится ли она сама).
4. Если ответ на предыдущем шаге положительный, то записает в бесконечном цикле, а если отрицательный, то останавливается.

Теперь запускаем сконструированную МТ. Зависнет ли она?

Видите противоречие? Если нет, давайте в терминах языков программирования.

Мы допустили существовании программы, которая принимает на вход другую программу с ее входыми данными и узнает, зависнет ли она. Назовем эту гипотетическую программу H.

Имея программу H, легко написать другую программу, назовем ее N, которая сначала записывается себя в память, потом запускает H, чтобы проверить, виснет ли она (N), а затем если виснет, то выходит, а если нет, то зависает.

Противоречие, опять же, видно, если попровобвать ответить на вопрос, зависнет ли N.

Подозрительно звучит, не правда ли? Но не нужно беспокоится, во-первых, ошибки в логие тут нет (даже если мои объяснения не очень строгие), а во-вторых есть и другие доказательство этого удивительного факта.

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

И все же, сколько это, один бит?

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

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

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

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

K(ww) ≤ K(w) + C.

Причем, новая программа не зависит от исходной строки w, то есть константа C одна для всех w, что на математическом языке записывается так:

∃C | ∀w K(ww) ≤ K(w) + C.

Почему меньше или равно, а не просто равно? Помните определение? Там говорилось, что K(w) -- это длинна наикратчайшей программы и входных данных, а мы просто привели один из вариантов -- нет никакой уверенности, что наша программа лучшая из возможных.

Итак, информации в сообщении ww лишь на константу больше, чем в w, а вовсе не в два раза.

Это вполне соответствует нашей интуиции. Но вот менее очевидный вопрос: сколько информации в сообщении uw, если известно сколько в u и сколько в w?

Так как строки u и w в общем случае не имеют ничего общего, то интуиция подсказывает, что количество информации суммируется. Но мы же хотим знать точно. Давайте разберемся подробно. Пусть K(u) = m, а K(w) = n, то есть некая программа приняв на вход строку x, выводит u, а другая приняв на вход y, выводит w, причем длинна первой плюс длинна x равна m, а длина второй плюс длинна y -- n. Также не забываем, что эти программы и их входные данные -- кратчайшие из всех возможных.

Теперь попытаемся найти программу (желательно короткую, чтобы получить хорошую оценку), которая принимает некую строку и выводит uw. Сложность тут в том, что мы ничего не знаем ни про u и w, ни тем более про x и y. В худшем случае x и y -- несжимаемые строки. (Про несжимаемые строки в терминах колмогоровской сложности, я расскажу в другой раз, а пока для нам подойдет интуитивное понятие.) Что же делать? Давайте расслабимся, нам не обязательно конструировать наикратчайшую программу генерации uw, можно сконструировать любую и мы получим хоть какую-то оценку, а потом уже можно ее улучшать, пока не будет пора на работу.

Как вам такой вариант: напишем программу, которая принимает на вход программу генерации u и ее входные данные x, а также программу генерации w и ее входные данные y, запускает первую, запускает вторую, а результаты конкатенирует. На выходе будет uw. Длина такой программы опять же константа, что дает легко выписать самую тупую оценку K(uw) ≤ K(u) + K(w) + C.

И все было бы хорошо, если бы мы и правда могли закодировать программы генерации u и w с их входными данными, используя ровно K(u) + K(w) двоичных цифр. Но это невозможно: если мы тупо припишем одну программу к другой, мы потеряем информацию о том, где первая кончается и начинается вторая.

Самый простой способ не потерять границу между строками -- записать сначала длину первой строки. Но тогда как отделить длину? Ну, скажем, мы может сначала записать длину длины, а потом только длин, а потом уже строки. Но что тогда делать с длинной длинны? Давайте так: сначала длину длины длины, потом длину длины, потом длину… М-да.

Постойте, помните как мы кодировали сообщение “N раз M”? Мы просто записали N в виде двоичной строки, причем каждую цифру продублировали, а в конце записали разделитель 01. Давайте воспользуемся этим способом.

Вы еще помните о чем я? Ах да, количество информации в строке uw. Саму программу для генерации uw мы уже написали (точнее я убедил вас, что ее можно написать), теперь нужно внимательно посчитать ее длину вместе с входными данными, то есть программами генерации u и w.

Итак, длина самой программы константа, скажем C. Длина входных данных -- это длина программы генерации u, то есть K(u) плюс длина программы генерации w, то есть K(w), плюс столько, сколько мы потратим на разделитель, а это 2×log2 K(u) + 2, если мы решили закодировать длину первой программы используя вышеописанный метод.

Итого количество информации в строке uw:

K(uw) ≤ K(u) + K(w) + 2×log2 K(u) + C (тут я включил 2 в константу C).

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

K(uw) ≤ K(u) + K(w) + log2 K(u) + 2×log2 log2 K(u) + C.

Можно так продолжать улучшать оценку, но ясно, что достичь K(u) + K(w) + log2 K(u) + C нам не удастся.

Помните, я вначале сказал, мол давайте выпишем сначала какую-нибудь оценку, а потом будем ее улучшать. Оказывается, что уже доказано, что оценка с одним логарифмом недостижима, а приближаться к ней мы можем используя наш тупой метод кодирования, добавляя “длину длины длины длины...” сколько-угодно раз. Так что остановимся на этом.

Один бит – сколько это?

Все просто, один бит – это количество информации, передаваемое одним бинарным сообщением, то есть одним сообщением из двух возможных. Например, ответ да/нет, 0/1 или влево/вправо.

Но не на столько просто. Важно, чтобы соблюдались два условия: третий варианта ответа невозможен и у вас до этого не было никакой информации о заданном вопросе. То есть, если вы спрашиваете у вашей новой знакомой, замужем ли она, то ее ответ почти никогда не будет содержать ровно один бит инормации. И не только потому, что кроме ответов да/нет она может ответить “не ваше дело” или “раведена”, но еще и потому что вы заранее можете оценить вероятность того, что она замужем: по ее возрасту, по поведению или по кольцу на пальце.

Хорошо, дальше все легко, два бита – это в два раза больше, чем один. Но что именно означает “в два раза больше”?

Во-первых, для простоты давайте абстрагируемся от формы ответа и будем считать, что один из двух возможных ответов всегда 0, а другой – 1: нет – 0, да – 1 или влево – 0, вправо – 1 и т. д.

Итак, двумя битами можно, например, представить информацию о маршруте, на котором есть две развикли, то есть всего четыре маршрута: дважды влево, влево-вправо, вправо-влево и дважды вправо. Нетрудно посчитать, что если маршрутов восемь, то для выбора одного из них, нужно три бита. А в общем случае, для кодирования одного из N состояний (о которых у нас нет предварительной информации), требуется log2 N бит.

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

На самом деле нет. Жизнь была бы слишком простой.

Где-то в этих рассуждениях есть фундаментальная ошибка. В самом деле, посмотрите на следующие два сообщение, где каждый бит закодирован цифрами 0 и 1:

первое: 010010111010001011100100101010011110,

второе: 010101010101010101010101010101010101.

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

М-да. Что же делать? Не то, чтобы предыдущее определение было полностью неверным, но оно не соответствует нашему интуитивному пониманию информации.

Интуитивно, в первом сообщении больше информации, потому что оно выглядит более случайным. А еще важнее то, что если вы захотите продиктовать обе последовательности по телефону, то в первом случае трудно придумать что-то более оптимальное, чем просто проговаривание цифр одна за другой, в то время как для передачи второго, можно просто сказать “восемнадцать раз 01”.

Может быть правильно было посчитать сколько информации в сообщении “восемнадцать раз” и добавить два? Это можно попытаться сделать: записать восемнадать в двоичной системе – 10010, а потом закодировать понятие “раз”: запишем 0, если следующие цифры – непосредственно само сообщение, и 1, если используется формулировка “N раз M”, где M – сообщение, которое предполагается повторить N раз. Саму формулировку “N раз M” запишем так: сначала N в двоичной системе, причем каждую цифру запишем дважды (00111100 вместо 0110), затем цифры 01, а затем сообщение M. Цифры числа N будем дублировать, чтобы было понятно, когда заканчивается N и начинается M, 01 будет играть роль разделителя, ведь если его пропутить, то если M начинается с двух одинаковых цифр, то будет непонятно, это окончание N или начало M.

Этот нехитрый трюк позволяет записать исходное сообщение из 18 пар 01 строкой 111000011000101, а это всего 15 бит. Правда сообщения из цифр, в которых нет повторяющихся последовательностей, придется записывать по-прежнему полностью, да еще и в придачу приписывать ко всем 0, чтобы отличить их от закодированных.

Зачем все это? Ах да, мы хотели оценить количество информации в сообщении таким образом, чтобы чтобы это больше соответствовало нашему интуитивному понятию информации. Получается в нашем исходном первом сообщении 19 бит информации, а во втором – 15. Что ж, это уже лучше. Немного смущает тот факт, что в первом сообщении мы теперь считаем один “лишний” бит, но зато наша оценка больше соответствует нашей интуиции: во втором сообщении информации меньше.

Ну как, удалось ли мне вас убедить, то такая оценка лучше, чем простой подсчет цифр?

Сомневаюсь.

Но нельзя сказать, что идея совсем безнадежна. Не будем ее отбрасывать, а вместо этого попробуем ее немного улучшить.

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

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

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

001001011001010100011000010000010110

101001000100001000001000000100000001

Потому что, опять же, если представить, что мы заходим его продиктовать по телефону, скорее всего мы скажем что-то вроде “восемь единиц, разделенных нулями, причем количество нулей увеличивается каждый раз на один, то есть один, ноль, один, два нуля, один, три нуля и т. д.”

Эта формулировка кажется длинной и запутанной, и возможно на практике некоторые предпочтут проговорить все цифры как есть, но я готов поспорить, что если бы эта последовательность состояла из миллиона цифр, то вы бы поменяли свое мнение.

Тогда можно действовать по старому плану: придумать как закодировать нулями и единицами фразы типа “N единиц, разделенных нулями...” и т. д.

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

А кроме того, как быть, если одну и ту же строку можно закодировать несколькими способами?

На этот вопрос есть простой ответ, который предложил Рей Соломонофф в 1960 году.

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

Понятно?

Нет? Давайте по-порядку. Универсальная машина Тьюрига – это открытие, которое сделал Тьюринг в 1936 году. Оно описано в статье под названием “О вычислимых числах с приложением к проблеме разрешимости” на 36 страницах.

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

Сегодня этим вряд ли кого-то удивишь. Все современные, и не очень, компьютеры обладают этим свойством. Вы покупаете компьютер не под конкретную задачу, а универсальный. Какую задачу он будет решать, зависит от того, какую программу вы на нем запустите. Но в 1936 году это было фундаментальное открытие. До Тьюрига все создаваемые машины проектировались для выполнения одного конеретного алгоритма.

Если вы заинтересовались, я рекомендую прочитать книгу Пецольда “Annotated Turing”, в которой подробно, абзац за абзацем, разбирается работа Тюринга 1936 года. Ну а самые стойкие могут прочитать оригинальную статью.

В любом случае, какое отношение это имеет к нашей оценке информации? Универсальная машина Тьюрига – это, по просту говоря, компьютер с бесконечной памятью. Он считывает программу, записанную в памяти (в МТ – на ленте), и выполняет ее. Входные данные берутся тоже из памяти (записаны рядом на ленте).

Так вот, для оценки количества информации в сообщении, мы выпишем все возможные программы и их входные данные, такие, что результатом работы этих программ является наше сообщение. Самую короткую их этих программ (и ее иходные данные) мы и будем считать самым лучшим представлением сообщения, а ее длинну, опять включая входные данные, – количеством информации в нем.

Естественно, перебрать все возможные программы, не так-то просто. На самом деле, дела обстоят еще хуже – это сделать в общем случае невозможно. Если вам интересен этот вопрос, я рекомендую книгу Майкла Сипсера, в которой очень понятным языком описываются техники доказательства теорем о вычислительной неразрешимости различных проблем. Но для наших целей это не так уж и важно.

В самом деле, не всегда важно знать точное количество информации в сообщении, если есть возможность ее оценивать прибилизительно или сравнивать различные сообщения “по информативности” между собой.

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

А то, что я описал, называют дискриптивной сложностью, или просто сложностью. В некоторых источниках ее еще называют сложностью Колмогорова-Хайтина, а также алгоритмической энтропией, а также другими очень умными, но мало о чем говорящими, словами.