Книги: сентябрь

[egorius]

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

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

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

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

Где мудрость, которую мы потеряли в знанье? Где знанье, которое мы потеряли в сведениях?
— Томас Стернз Элиот

Ой-ой-ой, мне кажется, это плач читателя,
Вот бессмысленные вирши: признаюсь, они мои.
— Томас Фриман

Ощущение, что книг слишком много, порождало производство еще большего количества книг.
— Энн Блэр

Красота в глазах смотрящего, а информация — в голове у получателя.
— Фред Дрецке

...это была бы вещь очень достойная и прибыльная не менее, чем достойная...
— Ричард Малкастер об издании английского словаря в 1582 году

Дональд Кнут, «Древние вавилонские алгоритмы» (англ.)

Дважды меня спрашивали: Г-н Бэббидж, если вы введете в машину ошибочные числа, она выдаст правильный ответ? ... Я не в состоянии постигнуть, что за путаница идей могла спровоцировать этот вопрос.

На новом языке думать и рассуждать всегда трудно.

— Чарльз Бэббидж

Чарльз Дибдин в 1794 году сочинил песню про телеграф:

If you'll only just promise you'll none of you laugh,
I'll be after explaining the French telegraph!
Amachine that's endow'd with such wonderful pow'r,
It writes, reads, and sends news fifty miles in an hour.

и так далее. Чем не Telegraph Road!

Телеграфный стиль вытесняет все формы вежливости. Передать Могу ли я просить оказать мне любезность? на 50 миль стоит 6 долларов. Сколько таких бесполезных, но милых фраз должен безжалостно выкинуть наш бедный парень, чтобы сократить счет до приемлемой суммы?
— Эндрю Уинтер

А потом удивляемся, что теперь-де так не пишут...

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

Сейчас из-за ошибки в один символ не туда улетает ракета, а в 1887 году ошибка в одну букву обошлась торговцу в 20 тысяч долларов.

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

Они спокойнее, не пьют пиво и всегда под рукой.
— В. Х. Экерт о превосходстве телефонных операторов-девушек над мальчиками.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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