Размышления о думающих машинах. Тьюринг. Компьютерное исчисление
Шрифт:
В начале Второй мировой войны британцы перехватили из немецкого лагеря сигналы, которые, к их удивлению, не использовали код Морзе и не были зашифрованы «Энигмой». Речь шла о сигналах машины Лоренца, соединенной с телетайпом, которой немцы также успешно пользовались.
В Блетчли-парке все немецкие сигналы телетайпа называли ключевым словом Fish («рыба»), а сигналы, кодированные машиной Lorenz SZ40/42, получили кодовое название Tunny («тунец»). Так же как это было в случае с «Энигмой», британцы смогли выяснить подробности работы машины Лоренца благодаря счастливой случайности и ошибкам немцев, хотя на этот раз сама машина в их руки не попадала. В Блетчли-парке была создана электромеханическая машина, использующая аналогичный принцип и способная расшифровывать сигналы машины Лоренца. Ее называли Tunny Machine («Машина-тунец»). Как же функционировал Lorenz SZ40/42? Когда записывался один знак, он трансформировался в другом коде — коде Бодо, придуманном в 1874
Машина Lorenz SZ42.
Метод, используемый машиной Лоренца для шифровки сообщения, состоял в генерировании случайной пятибитной последовательности с помощью серии из 12 зубчатых колесиков (по-английски pinwheels), каждое из которых имело определенное количество контактов. Эти контакты могли быть в положении on(1) или off(0). Таким образом, при вращении получалась последовательность нулей и единиц, или бит. Если контакт был в активном состоянии, on, значение бита, соответствующего кодируемой букве, менялось: с 0 на 1, с 1 на 0. Когда контакт был в неактивном состоянии, off, значение сохранялось. Далее применялся булев оператор XOR («исключающее или») между каждым из битов знака и измененного знака. Таблица данного оператора может быть представлена в следующем виде.
А
в
A XOR B
0
0
0
0
1
1
1
0
1
1
1
0
Эта процедура повторялась несколько раз последовательно до трансформации исходного знака в другой в кодировке Бодо. Например, если мы хотим зашифровать фамилию TURING, сначала мы должны записать ее в виде кода Бодо. Получим последовательность 10000-00111-01010- -00110-01100-11010. Представим, что мы уже зашифровали последовательность знаков TURIN, а сейчас должны приступить к шифрованию последней буквы фамилии. Следующим шагом, если оператор машины настроил конфигурацию контактов диска, который мы назовем R1, как on-on-off-off-on, последовательность 11010, представляющая букву G, трансформируется в 00011, но такая последовательность соответствует букве А. Повторим эти шаги еще раз. Представим, что оператор машины настроил второй диск, который мы назовем R2, расположив контакты как on-off-on-off-on. В этом случае последний диск трансформирует последовательность 00011 и превратит ее в 10110, которая, согласно коду Бодо, соответствует Р. Таким образом, с помощью машины Лоренца мы зашифровали букву G как Р.
COLOSSUS: РОЖДЕНИЕ КОМПЬЮТЕРА
Часто оказывается так, что достижения науки и техники относятся к позитивным результатам военных конфликтов. Именно так произошло и с Colossus. В Блетчли-парке была создана первая электронная программируемая машина, которая с некоторыми ограничениями может называться компьютером. Если Bombe была ответом на «Энигму», Colossus стал ответом на Lorenz SZ 40/42. Машина Лоренца шифровала сообщения, используя последовательность случайных чисел. Эти числа получались с помощью электромеханического метода, в котором использовались шестеренки (pinwheels). К счастью, полученные таким способом числа имели псевдослучайный характер по сравнению с числами, которые вытаскивают из лотерейного барабана, поскольку существовали правила получения их последовательности. Этот факт обеспечил успешную расшифровку перехваченных сообщений.
Начинка Colossus была позаимствована у машин Робинсона, которые представляли собой семейство аппаратов, разработанных для расшифровки сообщений, кодированных машиной Лоренца. В машине Робинсона использовались две ленты: одна с зашифрованным сообщением, другая с последовательностью случайных чисел, полученных на дисковой системе, подобной машине Лоренца. Усовершенствование Colossus состояло в замене второй ленты — последовательности случайных чисел — электронными ламповыми комбинациями. Серьезным недостатком машин Робинсона было то, что вторая лента довольно часто и неожиданно рвалась, так как для чтения случайных чисел требовалась высокая скорость. Colossus не имел такого недостатка и мог считывать до пяти тысяч знаков в секунду, что было важным достижением той эпохи. Хотя лично Алан Тьюринг не участвовал в разработке Colossus, этой машиной занимались его учителя, среди которых Макс Ньюман, и коллеги из Блетчли-парка.
Первый вариант этого «компьютера» был создан Томми Флауэрсом (1905-1998), инженером Исследовательской станции Центрального почтамта. Он предложил новую идею, состоящую в использовании электронных ламп, тех же, что и в схемах первых радиоприемников. Так появился первый в истории электронный компьютер. Схема Colossus состояла из невероятного количества в 1500 ламп — именно они использовались в компьютерах, созданных до 1959 года.
ПОСЛЕДОВАТЕЛЬНОСТИ СЛУЧАЙНЫХ ЧИСЕЛ
Компьютер — это универсальная машина Тьюринга. При определенном его состоянии и передаче на вход определенных данных будут выполнены некоторые операции, что приведет к полностью предсказуемому результату. Например, если на листке для расчета бюджета мы запишем определенные числовые данные, input, то результат, output, будет всегда один и тот же. Одной из самых интересных задач науки со времен Джона фон Неймана, который одним из первых поднял этот вопрос, стало получение алгоритмов, генерирующих последовательность чисел случайно, как если бы мы доставали номера из лотерейного барабана. Если числа, получаемые путем доставания из барабана, называются случайными, то числа, выдаваемые компьютером, называются псевдослучайными. Компьютерная программа, с помощью которой мы можем получить такие числа, называется генератором случайных чисел. Псевдослучайные числа находятся в интервале [0,1]. Например, последовательность двенадцати чисел 0,092833; 0,472751; 0,542341; 0,022788; 0,069853; 0,317325; 0,808213; 0,225401; 0,633599; 0,133044; 0,530186,0,477541 получена в следующей программе на BASIC-256:
п=0
do
u=rand
print u
n=n+l
until n=12
Приведем другой пример: как можно с помощью данной программы сделать симуляцию игрального кубика? Мы просто заменим u=rand на и= =int (rand*6) + 1. Числа, получаемые с помощью программы, имеют определенные характеристики. В частности, они должны находиться в интервале между 0 и 1, должны быть независимы друг от друга, то есть если мы получаем число 0,808213, оно не должно влиять на следующее число последовательности, 0,225401. Также обязательным для таких чисел является условие равной возможности их получения. Любопытно, что эти числа по отдельности не являются случайными, их случайный характер проявляется только в последовательности, частью которой они являются и статистические характеристики которой подобны последовательности чисел, полученных с помощью механической системы лотерей. Сегодня существует возможность получить в интернете настоящие случайные числа, взятые из физических явлений, что заменяет алгоритм, подобный которому использовался в функции rand BASIC-256.
ЭЛЕКТРОННЫЕ ЛАМПЫ И ЛОГИЧЕСКИЕ ВЕНТИЛИ
Электронная лампа представляет собой вакуумную трубку, в которой имеются нить накаливания, испускающая электроны, — катод (отрицательный заряд), и металлическая пластинка, принимающая электроны, — анод (положительный заряд). В результате мы получаем ток электронов от катода при его накаливании к аноду. Так как ток проходит только в одном направлении, такая лампа реализует функцию важнейшего электронного компонента — диода. Впоследствии в диод добавили дополнительную нить — сетку между катодом, испускающим электроны, и анодом, получающим их. При приложении тока к сетке можно контролировать ток электронов от катода к аноду, увеличивая напряжение. Эта дополнительная нить лежала в основе нового изобретения — триода, электронного компонента, выполнявшего функцию современного транзистора. С помощью этих электронных компонентов можно создавать схемы, выполняющие арифметические операции, например суммирование, или логические операции, например сравнение чисел.
Два вида ламп: диод (слева) и триод (справа).
Нули и единицы
В компьютерах, в том числе в Colossus, арифметические и логические операции осуществляются на основании булевой алгебры, оперирующей битами, то есть числами 0 и 1, с применением к ним операторов, называемых на языке электроники вентилями. Предположим, ток в 0 В представляет число 0, а ток 3 В представляет 1. Следовательно, факт, проходит или не проходит электрический ток, определяет величина 0 или 1, а это один бит, то есть наименьшее количество информации, которую может обработать компьютер. Вентиль — электронная схема с диодами или транзисторами, в которой О или 1 на входе трансформируются на выходе также в 0 и 1 в результате применения одного из операторов булевой алгебры. Из всех возможных операторов самыми используемыми в цифровой электронике являются И и ИЛИ. Вентиль И, эквивалентный на логическом уровне союзу «и», на выходе дает 1, если на всех входах одновременно получено 1. С другой стороны, на выходе будет 0, если на одном или двух входах получен 0. Ниже приводится таблица и символ для этого вентиля.