Пиксель. История одной точки - Элви Рэй Смит

сделал и Черч, а также еще несколько ученых. Но в сравнении с привлекательностью метода Тьюринга все остальные подходы померкли. Мы до сих пор используем понятия, которые он ввел в своей основополагающей статье 1936 года. Особенно прижилось его слово computable — «машинно-вычислимый». Он также выдвинул саму идею программирования, хотя и не использовал это слово. Фактически он был первым программистом. Также, увы, именно он первым написал неисправное программное обеспечение.

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

Ньюман очень переживал, что Тьюринг превращается в «замкнутого одиночку», и поделился опасениями с Черчем. Он полагал, что общение с математической элитой Принстонского университета — с людьми, говорящими с ним на одном языке, — могло бы обратить усиливающуюся нелюдимость вспять. Поэтому он попросил Черча взять Тьюринга к себе в качестве аспиранта, и тот снова согласился. Тьюринг получил докторскую степень в Америке под руководством Черча.

Тьюринг отправился в США на пароходе «Беренгария» и высадился на Манхэттене в сентябре 1936 года. По случайному совпадению Котельников совсем недавно, в мае, сошел на берег в том же месте и по трапу того же парохода. Советский ученый пробыл в США всего 60 дней и, вероятно, работал над секретным кодом в торговой компании «Амторг», офис которой располагался в центре Манхэттена. К тому моменту, когда Тьюринг прибыл в Нью-Йорк, Котельников уже уехал домой. Они, так сказать, разошлись, как в море корабли, хотя корабль был один и тот же.

Вскоре возникло еще одно любопытное совпадение. Тьюринг отправился из Нью-Йорка в находящийся неподалеку Принстон, чтобы продолжить там занятия под руководством Черча. Затем его наставник Ньюман тоже приехал на полгода в Принстон, в соседний Институт перспективных исследований (Institute for Advanced Study), который иногда называли Принcтитутом, чтобы не путать с Принстонским университетом и избежать уродливой аббревиатуры IAS. Джон фон Нейман — еще одна важная фигура в нашей истории — уже работал в Принституте в качестве одного из первых постоянных стипендиатов.

Не игрушка

Чтобы постичь великую идею Тьюринга, давайте взглянем на карточку из плотного картона, которая изображена на рисунке 3.2. У нее срезан один угол и сделано круглое отверстие в центре. Как на лицевой (с копирайтом), так и на оборотной стороне есть надписи. Кажущаяся простота этой карточки обманчива — не дайте себя одурачить: она обладает невероятной мощью.

Теперь представьте длинную бумажную ленту, расположенную за карточкой слева направо. Лента размечена на квадраты. Один из них вы можете видеть через отверстие в карточке. Квадраты в основном пустые, но на некоторых изображены символы. Я решил использовать цифры 1, 2, 3, 4 и 5, но их можно заменить и, например, на #,! $, % и &. Это просто некие условные символы, не обозначающие ничего конкретного. В частности, нужно понимать, что за цифрами не скрываются настоящие числа. Мы называем их символами, но они ничего не символизируют. Если вы замените 1 на #, 2 на! и так далее, ничего не изменится — кроме начертания меток на квадратах.

На рисунке 3.3 в верхнем ряду (шаг 1) показана лента, на которой всего четыре метки: 5155. Остальные квадраты пусты. Карта изображена слегка прозрачной, чтобы сквозь нее была видна лента. Колонка справа со странными изображениями — цифрами в кружках, двоеточиями, стрелками — содержит шесть правил, определяющих работу устройства. Каждому символу на ленте соответствует одно правило. Перевернутый список слева от отверстия содержит еще шесть правил.

Устройство работает следующим образом. В правой колонке найдите правило для символа, который видите в отверстии. (Пока что не обращайте внимания на перевернутые правила слева.) Для шага 1 это правило вверху справа — оно относится к пустой ячейке. После пробела стоит двоеточие, за которым следует цифра 5. Правило означает, что нужно заменить пробел цифрой 5 — написать 5 в пустой ячейке. После 5 идет стрелка влево. Нужно переместить карту на одну клетку в указанном направлении. Маленький символ еще правее обозначает саму карточку. Соответственно, вы должны повернуть карточку так, чтобы она соответствовала положению символа. В нашем случае нужно повернуть карту на пол-оборота по часовой стрелке, чтобы обрезанный угол оказался вверху слева и получилась конфигурация, изображенная во втором ряду (шаг 2).

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

Если проделать два следующих шага, получится конфигурация, изображенная на четвертой строке — шаг 5 (шаг 4 не показан). После них карта сохраняет ту же ориентацию (срезанный угол сверху слева). В этом случае применяется третье сверху правило в правой колонке: замените 2 на 3, переместите карту влево на один квадрат и поверните ее. Срезанный угол должен оказаться снизу слева. Нам откроются другая сторона карты (шаг 6) и еще два списка правил, отличающихся от тех, которые мы видели ранее.

Рис. 3.2

Рис. 3.3

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

Всё, что мы проделали, — вовсе не пустая забава. Хотите верьте, хотите нет, но в итоге она привела к появлению Цифрового Света. Устройство на карточке — это машина Тьюринга. Одна из его игрушек. Аппаратная реализация его самого известного изобретения.

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

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