egorius

Джеймс Глик, «Информация: история, теория, потоп»

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

Наверное, как популяризатор, Глик не сказал ничего нового для науки, зато сказал для меня.

Местами книга даже напоминает любимый Криптономикон Нила Стивенсона. В ней к тому же упомянут и его прообраз — книга Джона Уилкинса о криптографии 1641 года и другие, реальные «коны»: Металогикон Иоанна Солсберийского, Католикон Иоганна Бальба.

Ричард Докинз, «Эгоистичный ген»

Для меня, ни разу не специалиста в биологии, показались интересными как минимум несколько идей (не говоря о том, что пришлось разобраться с митозом и мейозом).

Во-первых, единицей естественного отбора в теории Дарвина следует считать не вид и тем более не отдельную особь, а ДНК (или «ген») — нечто, реплицирующее себя и определяющее свойства несущих его организмов. Носитель используется репликантом (а не наоборот) для того, чтобы передать свои копии носителям следующего поколения.

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

В-третьих, репликантами могут быть не только ДНК, но и даже нечто нематериальное, например мемы (которым Глик посвятил целую главу). Для возникновения естественного отбора достаточно появления репликантов в условии ограниченных ресурсов, вне зависимости от их природы.

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

Эксперименты автора с компьютерным моделированием эволюционных стратегий напомнили мне старую забаву программистов: core wars. Интересно было бы провести турнир по «эволюционным правилам», то есть чтобы количество копий программы в следующем раунде определялось ее успехами в предыдущем.

Чарльз Петцольд, «Читаем Тьюринга»

Будучи неравнодушным к Машинам Тьюринга (proof), я не мог пройти мимо этой книги, да и с Гликом она пересекается очень сильно. Чтение для маньяков: очень много математических подробностей, за ходом рассуждений сложно следить, даже будучи знакомым с МТ.

Речь идет о знаменитой статье Тьюринга 1936 года On Computable Numbers, with an Application to the Entscheidungsproblem, в которой доказывается неразрешимость логики предикатов первого порядка. Логика включает в себя переменные, логические связки (∧, ∨ и ¬) и кванторы (∀ и ∃), а под неразрешимостью понимается невозможность описать алгоритм, определяющий истинность произвольной логической формулы за конечное число шагов.

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

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

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

Фактически, УМТ является универсальным компьютером, способным выполнить произвольную программу — если не считать Бэббиджа, эта концепция изрядно опередила время. Важнейшим следствием неразрешимости является невозможность в общем случае написать код, анализирующий другой код. Фактически, единственный способ понять, что делает произвольный код — это выполнить его.

Дальше Тьюринг устанавливает связь между МТ и логикой предикатов первого порядка, и проблема неразрешимости доказана.

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

Еще интересное: похоже, что стек тоже изобрел Тьюринг. Во всяком случае, он использовал операции bury и unbury в системе команд Automatic Computing Engine (ACE) в 1946 году.