Пиксель. История одной точки

Блетчли-Парк

В Блетчли-Парке Тьюринг, как известно, помог взломать схему шифрования, которую немцы использовали для военной радиосвязи. Немцы создали чертовски сложную шифровальную машину под названием «Энигма» (это ее настоящее фирменное наименование), которая напоминала старомодную пишущую машинку в деревянном футляре. Оператор вводил текстовое сообщение – скажем, от адмирала из штаба немецкого военно-морского флота для подводной лодки в море, – и машина кодировала буквы одним способом, затем кодировала полученные буквы другим способом и так далее. При помощи сменных роторов производилось шифрование в несколько слоев. Радист на подводной лодке настраивал свою принимающую «Энигму» в соответствии с передающей. Затем полученное сообщение расшифровывалось слой за слоем в обратном порядке, пока не получался исходный текст, который распечатывался для капитана субмарины. Немцы использовали систему одноразовых блокнотов для ежедневной перенастройки шифровальной машины. Напомню, и Котельников, и Шеннон доказали, что такую систему нельзя взломать – по крайней мере, при правильном использовании. Но немцы полагали, что она неуязвима из-за огромного количества возможных конфигураций. На самом деле они так до конца войны и не поняли, что Тьюрингу и его коллегам из Блетчли-Парка удалось найти слабые места. Взлому способствовали множество факторов: неправильное использование системы операторами, заведомо известные тексты сообщений (например, метеосводок), захваченные у противника машинки, – но ключевую роль сыграли вычисления, проделанные в огромных объемах. Вот тут и вступили в дело вычислительные машины.(Энигма была взломана в Домике № 8, который изображен на фотографиях B и C на рисунке 3.7. На фото А – эклектичный особняк по соседству.)

Метод проб и ошибок при расшифровке кода «Энигмы» подразумевал очень утомительную работу, которую сначала выполняли вручную сотни «вычислителей», «рабынь» Тьюринга. Чтобы облегчить утомительный труд и увеличить скорость декодирования, работавшие в Блетчли-Парке шифровальщики построили большие машины, которые они называли «криптологическими бомбами». Эти машины в современном смысле еще не были компьютерами, но уже определенно стали заметным шагом на пути к ним. В них отсутствовала возможность программирования даже с помощью аппаратных переключателей и кабелей. В некотором смысле «бомбы» допустимо назвать машинами Тьюринга, но не универсальными машинами Тьюринга. Они выполняли систематическую задачу, состоящую из множества шагов, – перебирали огромное количество способов шифрования, которые могла бы использовать «Энигма». Других вычислений они не выполняли. Электромеханические «бомбы» работали значительно быстрее «вычислителей» из плоти и крови. Скорость имела решающее значение, позволяя, скажем, предупреждать американские и британские торговые суда о зонах охоты немецких подводных лодок. Так что прогресс налицо: вычисления становились быстрее.

Макс Ньюман

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

Рис. 3.7

Тьюринг возглавил первую атаку на шифровальную машину «Энигма» с помощью «криптологических бомб». Теперь настала очередь Ньюмана. Он командовал второй волной атак, направленных против новейшей немецкой шифровальной машины по прозвищу «Танни» (словом tunny в Британии называют тунца). Здесь использовалась гигантская электронная счетная машина Colossus, первый прототип которой был построен в 1943 году и перевезен в Блетчли-Парк в 1944 году. К концу войны там действовало десять таких монстров. Все эти почти-компьютеры – пока что не компьютеры с хранимой в памяти программой – применялись для практических расчетов еще до появления почти-компьютера ЭНИАК в Америке.

Тьюринг косвенно повлиял на работу Colossus. Он пришел к математическому открытию, известному на сленге Блетчли как тьюринжизм, – оно и стало ключом к разгадке шифра. Удивительно, что он не принимал прямого участия в расшифровке кода «Танни», учитывая его отношения с Ньюманом и опыт работы с «бомбами в Блетчли-Парке. Но тогда – и еще какое-то время после – команда с Ньюманом у них не сложилась, потому что расшифровка текстов больше не занимала Тьюринга. Он увлекся кодированием голоса. Британское правительство поддержало интерес, отправив его обратно в Америку со специальной миссией.

Вокодер как связующее звено

Тьюринг и Котельников разминулись на Манхэттене в 1936 году, после чего так и не встретились, но тем не менее между ними существовала удивительная связь. Она заключалась не в компьютерах, теореме выборки или взламывании шифров, как вы могли бы подумать, а в вокодере (от английского voice coder – «кодировщик голоса»). Он связывает Тьюринга не только с Котельниковым, но еще и с Шенноном и даже с Солженицыным. Все они работали над вокодерами. Сейчас по сравнению с компьютером вокодер выглядит как тривиальный прибор. Но тогда это устройство казалось важным направлением в развитии технологий. По прошествии многих лет становится понятно, что оно привело ко многим достижениям в области цифрового света и звука.

Из главы 2 нам известно, что Котельников, а впоследствии и Шеннон доказали, что шифры, основанные на одноразовых блокнотах, устойчивы ко взлому. Вокодер, дополненный таким шифратором, сделал голосовые коммуникации столь же безопасными, как и письменные. Шифрованный вокодер – голосовой скрэмблер – был чем-то вроде «Энигмы» для голоса.

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

Черчилль и Рузвельт (а позже и Трумэн), хотя и действовали более рационально, также нуждались в голосовом шифраторе для связи в военное время, что привело к появлению системы Junior X. Ее разработка свела Тьюринга и Шеннона в Bell Labs в 1943 году. Британское правительство назначило Тьюринга экспертом по криптографии для проверки безопасности Junior X. Именно из-за этого он и не стал членом команды Ньюмана в Блетчли-Парке. Он ненадолго присоединился к Шеннону, который выступил экспертом с аналогичным заданием от американских властей. Из соображений безопасности им запрещалось обсуждать криптографию, но ничто не мешало говорить о машинных вычислениях, компьютерных шахматах и компьютере как модели человеческого интеллекта.

Примечательно, что многие герои истории пикселя участвовали в разработке вокодера, но для развития компьютеров еще важнее тот факт, что один из них создан непосредственно Тьюрингом. По предложению своего близкого друга Робина Ганди он назвал разработанный прибор «Далила» (Delilah) в честь библейской возлюбленной Самсона, выведавшей секрет его силы и предавшей его. Проектирование «Далилы» помогло Тьюрингу восполнить нехватку практического инженерного опыта. Это устройство еще не было компьютером, но опыт его разработки привел к созданию настоящей универсальной машины Тьюринга. Оно стало подготовительным этапом, чтобы покинуть башню из слоновой кости и уйти в вонючую лабораторию.

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

Сначала обратимся к идее частот Фурье. Мы разбиваем диапазон частот, используемых голосом, на, скажем, десять меньших диапазонов. Предположим, что частоты, необходимые для передачи человеческого голоса по телефонной линии, находятся в диапазоне от 0 до 3000 колебаний в секунду. (Голосовая связь обычно не использует весь спектр возможностей человеческого слуха, способного различать звуки высотой до 20 000 циклов в секунду.) Представьте этот диапазон частот разбитым на десять поддиапазонов по 300 циклов в секунду каждый. Например, все частоты в исходном голосовом сообщении с частотой менее 300 циклов в секунду относятся к диапазону 1, частоты от 300 до 600 циклов в секунду относятся к диапазону 2 и так далее. Грубая идея голосового скрэмблера состоит в том, чтобы перемешать десять диапазонов известным участникам коммуникации, но секретным способом, передать результат по линии связи, а затем расшифровать на принимающей стороне.

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

Самое удивительное, что теорема отсчетов тогда использовалась. Напомним, что речь идет о 1943 годе, а Шеннон опубликовал свою версию только в 1948-м. Очевидно, что принципы теоремы отсчетов уже полностью осознавались на Западе за пять лет до статьи Шеннона. Неудивительно, что тот же принцип использовался в СССР для их вокодеров, потому что Котельников обнародовал свою работу в 1933 году. Кроме того, вскоре и Тьюринг использовал принцип выборки в конструкции своей «Далилы». Он говорил, что задумал свою версию вокодера на борту корабля, когда второй раз возвращался домой из Америки в 1943 году.

Вокодер все еще с нами, но теперь в него встроен компьютер. В современной популярной музыке используют компьютерный аудиопроцессор, который называется автотюнер. Сегодня он применяется не для шифрования, а для корректировки тональности, избавления от фальшивых нот и улучшения голоса. Музыканты, которые к нему прибегают, такие как Шер, Лори Андерсон и Ти-Пейн, концептуально связаны с Тьюрингом, Котельниковым, Шенноном и Солженицыным. В какой-то степени их можно даже считать партнерами. Автотюнер – это фотошоп для человеческого голоса, потому что он позволяет многим певцам – не столь хорошим, как трое перечисленных, – добиться идеального звучания и попадания в ноты. Отсылка к Photoshop снова напоминает нам, что пиксели и соксели – это, в принципе, одна и та же идея. Мы можем создавать цифровой звук с нуля при помощи компьютеров так же, как и цифровой свет.

Непознаваемость

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

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

Аппаратное обеспечение ничего не говорит нам о программном. Даже заполучив полную электрическую схему компьютера, мы не поймем, что он вычисляет. Например, мы рассмотрели, как работает «аппаратное обеспечение» устройства из картонной карточки. Тем не менее полученных знаний недостаточно, чтобы понять любую из ее программ. Даже досконально зная, как устроен рояль Steinway, без партитуры вы не исполните этюд Шопена – его музыкальный софт. По такому же принципу вы можете создать полную электрическую схему человеческого мозга, но она не поможет вам понять, о чем думает этот мозг.

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

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

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

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

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

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

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

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

(1) Вычесть входное число x из входного числа y. (2) Если результат отрицательный, измените цифру в шаге 3 на 4, в противном случае измените ее на 5. (3) Перейдите к шагу 4. (4) Напишите «минус» и остановитесь. (5) Напишите «плюс» и остановитесь.

Давайте попробуем проделать это с x, равным 7, и y, равным 6: (1) 7 минус 6 равно 1. (2) Результат положительный, поэтому: (3) Перейдите к шагу 5. (5) Напишите «плюс» и остановитесь. Программа может быть не только неприятным переплетением ветвей и циклов, но еще и движущейся целью. Большинство современных операционных систем «защищают» программиста – как самоблокирующиеся автомобильные двери, – запрещая такой самомодифицирующийся код. Это слишком легко может посеять хаос. Тем не менее Тьюринг перенес эту идею в мир настоящих компьютеров. Свою инструкцию условного перехода для реального оборудования он реализовал с помощью самомодифицирующегося кода.

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

Программирование

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

– Дональд Э. Кнут. «Искусство программирования»

Программирование – секрет успеха универсальных вычислительных машин, но ученым потребовалось не менее десяти лет, чтобы понять это. Тьюринг опубликовал первые программы в своей знаменитой статье 1936 года «О машинно-вычислимых числах». Он написал их для концептуальных машин – машин Тьюринга, – которые демонстрировали концепцию универсальных машинных вычислений. Поэтому принято считать, что именно он изобрел программирование и концепцию хранимой в памяти программы. Он придумал слово computation (машинное вычисление), из которого родилось слово «компьютер», но слово «программирование» изобрел не он. Тьюринг использовал другой термин – «подготовка таблицы инструкций». Откуда же тогда взялось слово «программирование»?

Давайте более внимательно посмотрим, что на самом деле сделал Тьюринг. Предположим, ему понадобилась машина, которая переворачивает любую строку букв на входной ленте. Он разработал набор правил – таблицу инструкций – для конкретной машины Тьюринга, в которой реализована систематическая перестановка букв. Назовем ее машиной А. Затем он «скармливал» правила А универсальной машине. Вспомним рисунок, где изображены произвольная машина A и универсальная машина U, каждая со своей лентой. «Закодированные правила А» на этом рисунке – это то, что мы теперь назвали бы программой для А. Умная, интеллектуально интересная часть работы состоит в разработке таблицы инструкций для машины А, а не в ее кодировании в форму, требуемую для машины U. Кодирование – это простой и в чем-то даже механический набор действий. В нашем примере с машиной-карточкой эта работа заключается в замене пробелов на 0, записи лицевой ориентации карточки как f и так далее. Довольно рутинное занятие. Машине такое не надоест, а человек умрет от скуки.

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

Однако в конце 1940-х те, кто создавал первые аппаратные компьютеры, использовали термин setting up – предустановка, или настройка, – чтобы описать, как заставить машину выполнить необходимые вычисления. В более ранние времена почти-компьютеров – таких как ЭНИАК, например – этот процесс подразумевал необходимость прокладывать кабели и переключать тумблеры, поскольку иначе программу на оборудование было не установить. Позже, когда появились компьютеры с хранимой в памяти программой, настройка, по-видимому, стала означать не только создание программы, но и проверку, загружена ли она в память компьютера в нужном месте. Сначала казалось, будто инженеры построили вычислительную машину, а потом приступили к попыткам запустить ее.

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

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

В служебной записке от 5 сентября 1945 года везде, где был бы уместен термин «программирование», фон Нейман еще использовал слово «настройка», заключая его в кавычки. Он пишет: «Я хочу еще раз подчеркнуть, что такая гибкая и высокоавтоматизированная система „настройки“ машины для решения [различных] задач абсолютно необходима для научных целей и ее следует обдумать». Как бы мы это ни называли, говорит он, это абсолютно необходимо.

В письме от 1 ноября, на всякий случай в кавычках, предлагается альтернатива слову «настройка»: «Точное электронное устройство, которое мы планируем, конечно, превзойдет его [ЭНИАК] по скорости и гибкости (универсальный характер), и его будет по крайней мере гораздо легче „настроить“, или „запрограммировать“». То есть, по его словам, это уже не будут переключатели и кабели, как в случае с ЭНИАК.

И наконец, буквально через пару недель, 19 ноября, «настройка» окончательно исчезает. Теперь это программирование безо всяких извиняющихся кавычек. Третий документ – протокол собрания в офисе участника проекта Владимира Зворыкина. «Код, приведенный в следующей таблице, представлен просто для того, чтобы доказать, что эту работу можно выполнить. Перечисленных операций достаточно для полного программирования». Именно тогда появился прообраз не только программирования, но и кодирования.

Команда фон Неймана, по-видимому, подразумевала, что программирование должно быть творческой частью работы, а кодирование – рутинной, «секретарской задачей». Сегодня программисты называют себя кодерами, и они пишут код. Они подразумевают творческий аспект вне зависимости от термина. Они знают, что рутинная часть работы теперь возложена на саму машину.

Итак, в конце 1945 года команда фон Неймана, а возможно, и сам фон Нейман первыми использовали слово «программирование» примерно в том же смысле, в котором мы его понимаем сегодня. Тьюринг вскоре тоже употребил этот термин в своей лекции в 1947 году, но упомянул его лишь несколько раз в ограниченном контексте. Впрочем, независимо от наименования, довольно быстро выяснилось, что программирование, творческий аспект – это сложная часть машинных вычислений и для него необходимо разработать отдельную научную дисциплину. Благодаря этому повсеместно возникли факультеты компьютерных наук.

Программирование – это способ создавать пиксели, изображающие вымышленные миры. Оно расширяет возможности Цифрового Света от простой фотофиксации миров до их создания – от простой съемки пикселей до их вычисления.