Джордж и код, который не взломать - стр. 7

Взлом «Энигмы»

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

Воображаемое устройство

В 1936 году «компьютером», то есть «вычислителем», называли не машину, а человека, который что-то вычисляет. Машина Тьюринга, придуманная гениальным математиком Аланом Тьюрингом, – воображаемое устройство, способное воспроизводить всё, что делает в хо де расчётов человек-компьютер. То есть машина Тьюринга – не реальный прибор, а математическое устройство, позволяющее понять, что такое вычисление и чего можно достичь путем вычислений. В реальности такой машины быть не может: например, у неё должны быть и бесконечная «память», и неограниченное время работы, а ни то, ни другое невозможно.

Цепочка нулей

Действие, выполняемое машиной, описывается конечным списком зашифрованных инструкций. Представим себе очень длинную ленту, на которой написана очень длинная цепочка нулей (такая же длинная, как сама лента). Эта лента, которая тянется бесконечно в обоих направлениях (предположим, что она бесконечно длинная), – «память» вычислительной машины. Между нулями вкраплено конечное число единиц – они представляют введённые в машину «данные». На ленте установлено управляющее устройство (процессор). Процессор может читать ровно один символ, проходящий через него в данный момент, и может либо ничего с ним не делать, либо заменить на 0 или 1.

Процессор также включает в себя часовой механизм, который ритмично тикает, и с каждым тиканьем процессор читает символ, который видит в данный момент. Затем он может сделать одно из двух – в зависимости от того, что он прочёл, и от своего текущего состояния. Он может:

• изменить прочитанный символ на 0 или 1; сдвинуться по ленте на одну позицию влево или вправо; возможно, перейти в другое состояние; ждать следующего тиканья;

• сделать всё то же, после чего остановиться (отключиться).

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

Тогда правило для начала работы выглядит так: