От абака до транзистора: Почему следующий шаг — квантовый? Часть I

Заметка моя совместно с Gemini 2.5 Pro.
Я был в музее, где были стэнды с историей квантвого компьютера. Подавляющие большинство людей и идей в этой статье взято оттуда.

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

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

Но у этого триумфа был предел. Погоня за скоростью и мощностью привела нас к невидимой стене — фундаментальным законам физики, которые не позволяют уменьшать транзисторы до бесконечности. И здесь, в третьем акте, происходит неожиданный поворот. Чтобы двигаться дальше, мы вынуждены вернуться к истокам. Мы снова обращаемся к физике, но уже не к привычной механике, а к самому странному и фундаментальному ее разделу — квантовой теории. Мы учимся вычислять с помощью самих атомов и их удивительных свойств, открывая дверь в новую эру — эру квантовых компьютеров. Эта статья — история о том, как, пройдя полный круг, вычисления вновь воссоединяются с физикой, чтобы совершить следующий великий скачок в будущее.

В первой части я опишу преисторию от 1800-ых (машина Бэббиджа) до 1950-ых (ENIAC).

Ниже есть продолжение.

Когда компьютер был из камня, воды и шестеренок

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

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

Вершиной этого подхода стала эпоха промышленной революции, когда сложность задач резко возросла. Для безопасности глобальной торговли и предотвращения морских катастроф требовалось точно предсказывать время приливов и отливов в портах по всему миру. Легендарный физик лорд Кельвин создал для этого удивительную машину — механический предсказатель приливов. Этот аналоговый компьютер использовал сложную систему из сотен шкивов, шестерней и ремней, чтобы физически моделировать гравитационное воздействие Луны и Солнца на океан. Все эти устройства были гениальны в своей узкой задаче, но абсолютно бесполезны для любой другой. Они были «однозадачными». Но что, если бы можно было создать машину, способную решать не одну, а любую задачу, которую можно представить в виде последовательности шагов? Эта дерзкая, революционная мысль родилась в голове викторианского гения, опередившего свое время.

Викторианский пророк и механическая мечта

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

Первым грандиозным проектом Бэббиджа была разностная машина — колоссальный механический калькулятор из латуни и стали. Ее цель — автоматическое создание математических таблиц. В ее основе лежал элегантный математический принцип: интерполяция при помощи полиномов. Идея в том, что любую сложную функцию, необходимую для навигации или баллистики (например, sin(x)), на небольшом отрезке можно с высокой точностью приблизить более простым многочленом, вроде y = ax³ + bx² + cx + d. А для таких полиномов работает гениальный трюк, известный как метод конечных разностей.

В основе идеи Бэббиджа лежит фундаментальное свойство функций, которое строго описывается аппроксимационной теоремой Вейерштрасса. Если говорить просто, эта теорема утверждает, что любую непрерывную функцию на заданном отрезке можно приблизить многочленом с любой желаемой точностью. Это значит, что для графика непрерывную функцию на отрезке [a,b], будь то синусоида или логарифм, можно подобрать такой полином, чей график на этом отрезке будет "почти неотличим" от исходного. Согласно этой теореме, если у нас есть n+1 опорных точек, то существует единственный многочлен степени не выше n, который точно проходит через все эти точки. Именно его и использовала машина для расчетов. Машина Бэббиджа как раз и была создана для вычисления значений таких "интерполяционных" полиномов.

Хотя машина Бэббиджа напрямую обрабатывала только полиномы, аппроксимационная теорема Вейерштрасса гарантирует, что любую непрерывную функцию на отрезке [a,b] можно сколь угодно точно приблизить полиномом. Это означает, что метод конечных разностей и таблицы полиномов применимы не только к заранее заданным многочленам, но и к синусу, логарифму, экспоненте и другим функциям, которые встречаются в навигации и инженерных расчетах. Машина, обрабатывая аппроксимирующий полином, фактически позволяет вычислять значения исходной функции с любой желаемой точностью.

Суть метода конечных разностей

Главный "трюк" метода заключается в свойстве полиномов: для любого многочлена n-ой степени его n-ный ряд конечных разностей является постоянной величиной. Например, рассмотрим простой полином y = x².

Значения функции: 1, 4, 9, 16, 25...

Первый ряд разностей Δy (насколько значение выросло): 3, 5, 7, 9...

Второй ряд разностей Δ²y (насколько выросла сама разность): 2, 2, 2, 2...

Разница второго порядка оказалась постоянной.

Теоретическое обоснование этого факта лежит в области дифференциального исчисления.

Обобщенная теорема о среднем значении для конечных разностей

Эта теорема устанавливает прямой мост между n-ной конечной разностью функции и ее n-ной производной.

Формулировка теоремы: Если функция f(x) имеет непрерывные производные до порядка n-1 включительно на отрезке [a, a+nh] и n-ю производную на интервале (a, a+nh), то существует такая точка кси $ξ \in (a, a+nh)$, что

Δⁿf(a) = hⁿ * fⁿ(ξ)

где Δⁿf(a) — n-я конечная разность функции f с шагом h, а
ξ — это некоторая точка внутри интервала (a, a+nh).

В нашем случае мы вычисляем таблицы для последовательных целых чисел, поэтому шаг h всегда равен 1. Это упрощает формулу до предельно изящного вида:

Δⁿf(x) = fⁿ(ξ)

где ξ — это некоторая точка внутри интервала (x, x+n).

1. Фундаментальное свойство полинома: Из дифференциального исчисления мы знаем, что n-ная производная полинома n-ой степени, Pⁿ(x), является константой. Например, для y = Ax³ + Bx² + Cx + D, третья производная y''' = 6A. Это просто число, оно не зависит от x.

2. Применяем теорему: Согласно обобщенной теореме о среднем значении для конечных разностей, n-ный ряд конечных разностей нашего полинома равен:

ΔⁿP(x) = Pⁿ(ξ)

Конечные разности оказываются дискретным аналогом производных:

* Первая разность (Δy) — аналог первой производной, показывающей скорость изменения функции.

* Вторая разность (Δ²y) — аналог второй производной, показывающей "ускорение" функции.

3. Соединяем факты: Правая часть этого равенства, Pⁿ(ξ), — это значение n-ной производной в точке ξ. Но мы только что установили, что эта производная — константа! Ей абсолютно неважно, в какой точке (ξ или любой другой) ее вычислять, она всегда будет одним и тем же числом.

4. Финальный вывод: Поскольку правая часть уравнения является константой, то и левая часть обязана быть той же самой константой.

ΔⁿP(x) = const

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

Представьте таблицу разностей. Чтобы найти следующее значение полинома, нужно:

1. Взять последнее известное значение (n-1)-го ряда разностей и прибавить к нему нашу постоянную n-ную разность. Так мы получим новое значение (n-1)-го ряда.

2. Затем взять последнее известное значение (n-2)-го ряда и прибавить к нему только что найденное значение (n-1)-го ряда.

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

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

Пример явного вычисления от начала до конца

Давайте рассмотрим полином третьей степени: y = x³ - 2x + 1. Наша цель — вычислить значения для x = 1, 2, 3, 4 и затем, используя только сложение, найти значение для x = 5.

Шаг 1: Вычисляем первые несколько значений функции. x = 1: y = 1³ - 2(1) + 1 = 0

x = 2: y = 2³ - 2(2) + 1 = 8 - 4 + 1 = 5

x = 3: y = 3³ - 2(3) + 1 = 27 - 6 + 1 = 22

x = 4: y = 4³ - 2(4) + 1 = 64 - 8 + 1 = 57

Наш ряд исходных значений (y): 0, 5, 22, 57

Шаг 2: Строим таблицу конечных разностей.

Первый ряд разностей (Δy):

5 - 0 = 5

22 - 5 = 17

57 - 22 = 35

Получили ряд Δy: 5, 17, 35.

Второй ряд разностей (Δ²y):

17 - 5 = 12

35 - 17 = 18

Получили ряд Δ²y: 12, 18.

Третий ряд разностей (Δ³y):

18 - 12 = 6

Получили постоянную разность Δ³y: 6.

Как и ожидалось, для полинома третьей степени третий ряд разностей оказался постоянным. Начальные значения для машины Бэббиджа были бы последними в каждом ряду: 57 (последнее значение y), 35 (последняя первая разность), 18 (последняя вторая разность) и 6 (постоянная третья разность).

Шаг 3: Используем разности для вычисления следующего значения (для x = 5).

Теперь мы "продлеваем" таблицу в обратном порядке, используя только сложение.

1. Находим следующую вторую разность:

Берем последнюю известную вторую разность (18) и прибавляем к ней постоянную третью разность (6).

18 + 6 = 24.

2. Находим следующую первую разность:

Берем последнюю известную первую разность (35) и прибавляем к ней только что найденную вторую разность (24).

35 + 24 = 59.

3. Находим следующее значение функции (y):

Берем последнее известное значение y (57) и прибавляем к нему только что найденную первую разность (59).

57 + 59 = 116.

Итак, мы вычислили, что для x = 5, значение y должно быть 116.

Проверка: Подставим x = 5 в исходную формулу: y = 5³ - 2(5) + 1 = 125 - 10 + 1 = 116. Результат совпал.

Именно этот процесс "проталкивания" сложений через ряды разностей и автоматизировала "разностная машина" используя для этого механические шестерни и рычаги.

Механика гениальности: шестерни, колонны и память.

Чтобы воплотить этот математический принцип в металле, Бэббиджу пришлось решить несколько блестящих инженерных задач. Представьте себе массивное устройство из бронзы и стали, высотой с человека. Его основу составляли вертикальные колонны (оси), каждая из которых предназначалась для хранения одного числа. На каждую такую ось были насажены числовые колеса, по одному на каждый десятичный разряд (единицы, десятки, сотни и т.д.). Каждое колесо имело гравировку с цифрами от 0 до 9.

* Память: "Памятью" машины, или, как называл ее Бэббидж, "складом", служил набор этих колонн. Каждая колонна была механическим регистром, который хранил одно число. Например, первая колонна хранила последнее вычисленное значение функции, вторая — значение первой разности, и так далее. Число физически кодировалось положением колес на оси: если на колесах колонны были видны цифры "0", "1", "1", "6", это означало, что в этом регистре хранится число 116.

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

Например, если колесо единиц в колонне Б показывало цифру "7", а на колесе единиц в колонне А была цифра "2", то колесо в колонне Б проворачивалось на две позиции (с 7 на 8, затем на 9) и останавливалось на цифре "9".

Гениальность же заключалась в механизме переноса единицы в старший разряд. Когда какое-либо колесо при вращении проходило через "9" и становилось на "0", специальный рычажок срабатывал и "подталкивал" соседнее колесо, отвечающее за следующий, более старший разряд (например, разряд десятков), заставляя его сдвинуться на одну позицию вперед. Это точный механический аналог того, как мы "переносим единицу в уме".

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

Увы, несмотря на годы работы и огромные по тем временам государственные вложения, разностная машина так и не была закончена при жизни Бэббиджа. Виной тому была запредельная для XIX века точность, требовавшаяся при изготовлении деталей. Однако история расставила все по своим местам: в XX веке энтузиасты из Лондонского музея науки построили рабочую копию по его оригинальным чертежам. Машина, состоящая из 8000 деталей и весящая 5 тонн, заработала безупречно, доказав — гениальный замысел Бэббиджа был абсолютно верен.

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

Увы, несмотря на годы работы и огромные по тем временам государственные вложения, разностная машина так и не была закончена при жизни Бэббиджа. Виной тому была запредельная для XIX века точность, требовавшаяся при изготовлении деталей. Однако история расставила все по своим местам: в XX веке энтузиасты из Лондонского музея науки построили рабочую копию по его оригинальным чертежам. Машина заработала безупречно, доказав — гениальный замысел Бэббиджа был абсолютно верен.

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

Ее архитектура пророчески предвосхитила современные компьютеры. В ней были:

* «Склад» (Store): Механическая память из сотен осей с числовыми колесами, способная хранить до 1000 чисел. Это был прямой аналог современной оперативной памяти (ОЗУ, RAM).

* «Мельница» (Mill): Арифметическое устройство, куда числа поступали со «Склада» для выполнения над ними четырех основных операций. Это был механический предок центрального процессора (ЦП, CPU).

* Система ввода/вывода на перфокартах: Гениальная идея, позволившая сделать машину по-настоящему универсальной.

Но как картонные карточки с дырками могли управлять сложнейшим механизмом из тысяч шестеренок? Идею Бэббидж позаимствовал у жаккардовых ткацких станков, где последовательность перфокарт определяла узор на ткани. Он развил эту логику: у Бэббиджа два типа перфокарт управляли машиной. Одни, «операционные карты», несли в себе инструкции (операции, которые нужно совершить: «сложить», «умножить»), а другие, «переменные карты», — адреса ячеек «Склада», откуда брать данные и куда записывать результат.

Это был революционный прорыв: впервые в истории программа была отделена от «железа».

Эта система позволила реализовать в механике три фундаментальных принципа, на которых строится любой современный компьютер.

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

2. Ветвление (Выбор): Самым революционным было то, что машина могла изменять ход своей работы на основе полученных результатов, реализуя логику «IF… THEN… ELSE…». Например, IF число в регистре X больше 100, THEN выполнить одну группу инструкций, ELSE — выполнить другую. Это была способность программы принимать решения.

3. Цикл (Повторение): Машина могла многократно выполнять один и тот же блок кода, пока не будет выполнено определенное условие. Инструкция могла звучать так: «Повторяй эту операцию, UNTIL значение в регистре Y не достигнет 1000». Это была концепция современных циклов while и for, воплощенная в металле.

Способность выполнять инструкции последовательно, ветвить вычисления в зависимости от результата и повторять их в циклах — это три кита, на которых стоит любое современное программирование. Именно этот необходимый и достаточный набор (то, что век спустя назовут Тьюринг-полнотой) и превращает устройство из простого калькулятора в универсальный компьютер.

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

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

Именно в них Ада не только опубликовала первую в мире сложную компьютерную программу (алгоритм вычисления чисел Бернулли), но и предвидела, что машина сможет оперировать любыми символами, а не только числами — нотами, буквами, изображениями, — и, например, создавать музыку. Это была та самая искра идеи о том, что компьютер — не просто калькулятор, а универсальный манипулятор информацией. В её честь в будущем назовут язык программирования — Ада.

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

Машина, которой не было

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

Представьте себе предельно простое устройство:

* Бесконечная лента, разделенная на ячейки, в каждой из которых может быть записан символ (например, 0 или 1).

* Считывающая головка, которая может смотреть на одну ячейку, читать символ, стирать его, записывать новый и двигаться по ленте влево или вправо.

* Простой набор правил (программа), который говорит головке, что делать. Например: «ЕСЛИ ты видишь символ 1, ТО сотри его, напиши 0, передвинь головку на одну ячейку вправо».

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

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

Война как катализатор: Взлом кодов и рождение гигантов

Идея Алана Тьюринга о "вычислительной машине" была гениальна, но абстрактна. Чтобы она изменила мир, ей нужен был катализатор. И им стала Вторая мировая война, превратившая секретный британский центр Блетчли-парк в настоящее горнило, где выковывались технологии будущего. Там, в тишине английской провинции, шла интеллектуальная война на два фронта, определившая исход многих сражений.

Фронт первый: механический хаос «Энигмы»

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

Как работала «Энигма»?

Представьте себе простое шифрующее колесо (ротор) всего с четырьмя буквами.

* Вход: A B C D

* Выход (внутренняя проводка): B D A C

Если вы введете букву "A", на выходе получится "B". Но магия «Энигмы» была в движении. После шифрования одной буквы ротор поворачивался на один шаг. Теперь его проводка смещалась:

* Вход: A B C D

* Выход (внутренняя проводка): C A D B

Теперь, если вы снова введете "A", то получите уже не "B", а "C". «Энигма» имела 3-4 таких ротора (из 5-8 на выбор), и каждый вращал следующий, создавая невероятно длинную последовательность шифров. Добавьте к этому коммутационную панель, где оператор вручную менял местами пары букв, и число комбинаций достигало 159 квинтиллионов. Весь этот ключ — порядок роторов, их начальное положение, настройки панели — менялся каждый день.

Как ее взломали?

Перебрать 159 квинтиллионов вариантов было невозможно. Машина «Бомба», созданная командой Тьюринга на основе довоенных польских наработок, действовала хитрее. Ее работа строилась на поиске логического противоречия с использованием "шпаргалки" (crib) — угаданного фрагмента текста.

Аналитики знали, что в немецких сводках погоды почти всегда есть слово "WETTER" (погода). Они брали шифротекст и предполагали: "А что, если вот эти 6 символов — это зашифрованное слово WETTER?". «Бомба» начинала проверку. Она имитировала работу «Энигмы» для этой гипотезы. Сотни ее вращающихся барабанов прогоняли возможные настройки. Если какая-то настройка приводила к логическому абсурду (например, буква 'W' шифровалась сама в себя, что в «Энигме» было невозможно), «Бомба» отбрасывала эту гигантскую ветвь вариантов и двигалась дальше. Так, вместо тупого перебора, она действовала как гениальный детектив, который отсекает ложные версии, пока не останется одна верная. За несколько часов она сужала океан возможностей до нескольких капель — вероятных ключей, которые уже можно было проверить вручную.

Фронт второй: цифровой призрак «Лоренца»

Но для связи между Гитлером и высшим командованием Вермахта использовался совершенно другой, на порядок более сложный шифр — «Лоренц» (Lorenz SZ42). Он был чисто цифровым, и против него электромеханическая «Бомба», созданная для имитации механики «Энигмы», была абсолютно бессильна.

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

Магия XOR и роковая ошибка оператора

Для начала нужно понимать:

1. Машина видела не буквы, а биты. «Лоренц» был приставкой к телетайпу, который использовал 5-битный код Бодо. Каждая буква представлялась комбинацией из пяти нулей и единиц (например, U = `10110`, R = `01010`).

2. Операция XOR работает на битах. XOR (или "исключающее ИЛИ") — это фундаментальная логическая операция, которая лежит в основе всего взлома.

Вот таблица истинности для операции XOR (иначе именуемое как сложение по модулю 2):

Вход A	Вход B	Результат A ⊕ B
0	0	0
0	1	1
1	0	1
1	1	0

Из этой таблицы следуют несколько важных свойств, которые позволили криптоаналитикам взломать шифр:

1. Самообратность: A ⊕ A = 0 (любое значение, сложенное с самим собой, дает ноль).

Доказательство: Рассмотрим все возможные значения A.

* Если A = 0, то выражение A ⊕ A становится 0 ⊕ 0. Согласно первой строке таблицы истинности, 0 ⊕ 0 = 0.

* Если A = 1, то выражение A ⊕ A становится 1 ⊕ 1. Согласно четвертой строке таблицы, 1 ⊕ 1 = 0.

Поскольку свойство выполняется для всех возможных значений A, оно доказано. Ч.т.д.

2. Свойство нуля (нейтральный элемент): A ⊕ 0 = A (любое значение, сложенное с нулем, не меняется).

Доказательство: Рассмотрим все возможные значения A.

* Если A = 0, то выражение A ⊕ 0 становится 0 ⊕ 0. Согласно первой строке таблицы, результат равен 0, что соответствует исходному значению A.

* Если A = 1, то выражение A ⊕ 0 становится 1 ⊕ 0. Согласно третьей строке таблицы, результат равен 1, что также соответствует исходному значению A.

Поскольку свойство выполняется для всех возможных значений A, оно доказано. Ч.т.д.

3. Коммутативность: A ⊕ B = B ⊕ A

Доказательство: Сравнив вторую (0 ⊕ 1 = 1) и третью (1 ⊕ 0 = 1) строки таблицы истинности, мы видим, что результат для разных входов не зависит от их порядка. Для одинаковых входов (0 ⊕ 0 и 1 ⊕ 1) порядок очевидно не имеет значения. Таким образом, свойство доказано для всех возможных входов. Ч.т.д.

4. Ассоциативность: (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)

Доказательство: Это свойство позволяет нам переставлять скобки в длинных выражениях. Докажем его, построив полную таблицу истинности для всех комбинаций A, B и C.

A	B	C	A ⊕ B	(A ⊕ B) ⊕ C	B ⊕ C	A ⊕ (B ⊕ C)
0	0	0	0	0	0	0
0	0	1	0	1	1	1
0	1	0	1	1	1	1
0	1	1	1	0	0	0
1	0	0	1	1	0	1
1	0	1	1	0	1	0
1	1	0	0	0	1	0
1	1	1	0	1	0	1

Поскольку два выделенных столбца полностью идентичны, мы доказали, что операция XOR ассоциативна. Это значит, что в выражении A ⊕ B ⊕ C нам не важен порядок вычислений. Ч.т.д.

Как был удален ключ

Теперь давайте посмотрим, как эти свойства позволили криптоаналитикам получить чистый текст.

Оператор начал передавать Текст 1. Связь прервалась. Он начал передачу заново (Текст 2) но с тем же ключом (что было строго-настрого запрещено; это была критическая ошибка). Обозначим Шифротекст 1 как C1, Исходный текст 1 как Т1, Шифротекст 2 как C2, Исходный текст 2 как Т2.

* C1 = Т1 ⊕ Ключ

* C2 = Т2 ⊕ Ключ

где ⊕ - это побитный XOR определённый выше.

Криптоаналитики вычислили C1 ⊕ C2. Для того чтобы понять почему, давайте посмотрим чему равно это значение.

1. Начальное выражение:
C1 ⊕ C2 =

2. Подставляем определения:
= (Т1 ⊕ Ключ) ⊕ (Т2 ⊕ Ключ)

3. Используем ассоциативность, чтобы перегруппировать члены:
= Т1 ⊕ (Ключ ⊕ (Т2 ⊕ Ключ))

4. Снова используем ассоциативность для внутреннего выражения:
= Т1 ⊕ ((Ключ ⊕ Т2) ⊕ Ключ)

5. Используем коммутативность для перестановки Ключ и Т2:
= Т1 ⊕ ((Т2 ⊕ Ключ) ⊕ Ключ)

6. И снова ассоциативность, чтобы сгруппировать два ключа вместе:
= Т1 ⊕ (Т2 ⊕ (Ключ ⊕ Ключ))

7. По свойству самообратимости Ключ ⊕ Ключ = 0. Подставляем:
= Т1 ⊕ (Т2 ⊕ 0)

8. По свойству нуля Т2 ⊕ 0 = Т2. Подставляем:
= Т1 ⊕ Т2.

ИТОГ: C1 ⊕ C2 = Т1 ⊕ Т2. Т.е. мы математически строго доказали, что наложение двух шифровок, использующих один и тот же ключ и побитный XOR, полностью уничтожает этот ключ, оставляя лишь результат сложения двух исходных текстов.

Теперт, давайте докажем, почему, зная шифротекст С1 и исходный текст Т1, можно найти Ключ.

Мы исходим из фундаментального уравнения шифрования:

* C1 = Т1 ⊕ Ключ

Наша цель — алгебраически выразить Ключ через известные нам C1 и Т1. Для этого посмотрим, чему равно значение C1 ⊕ T1.

1. Начальное выражение:
C1 ⊕ T1 =

2. Подставляем определение C1 из уравнения выше:
= (Т1 ⊕ Ключ) ⊕ Т1

3. Используем Коммутативность, чтобы поменять местами Т1 и Ключ.


= (Ключ ⊕ Т1) ⊕ Т1

4. Используем Ассоциативность, чтобы перегруппировать члены и поставить два Т1 рядом:
= Ключ ⊕ (Т1 ⊕ Т1)

5. Используем свойство Самообратности. Выражение в скобках (Т1 ⊕ Т1) равно нулю:
= Ключ ⊕ 0 6. По свойству нуля Ключ ⊕ 0 = 0
: = Ключ.

ИТОГ: C1 ⊕ T1 = Ключ. Таким образом, мы доказали, что для восстановления ключа достаточно сложить (операцией XOR) шифротекст с соответствующим ему открытым текстом.

Вот как это выглядело на практике. Оператор начал передавать Текст 1: SPRUCHNUMMER (означающий "номер сообщения"). Связь прервалась. Он начал передачу заново (Текст 2) с тем же ключом, но в этот раз сократил слово до SPRUCHNR и продолжил сообщение другими словами, например, DATUM... (дата...).

	...	N	U	M	M	E	R	...
Текст 1	...	N	U	M	M	E	R	...
Биты Т1	...	01100	10110	11001	11001	10001	01010	...
Текст 2	...	N	R	D	A	T	U	...
Биты Т2	...	01100	01010	01001	11000	00001	10110	...
Т1 ⊕ Т2 (биты)	...	00000	11100	10000	00001	10000	11100	...

Что увидели аналитики:

1. Длинная последовательность нулей (00000): Это соответствовало общей части SPRUCH_N.

2. Осмысленный "обрывок": Сразу за нулями шел результат U ⊕ R = 11100. Затем M ⊕ D и так далее. Это был уже нечитаемый "шум", но сам факт его появления после нулей указывал на точное место расхождения текстов.

3. Запуск цепной реакции: Зная типичную структуру немецких сообщений, аналитики предположили, что в первом тексте было слово SPRUCHNUMMER. Это позволило им:

* Вычислить первые ~12 символов ключа (Ключ = С1 ⊕ Т1).

* Используя эти символы ключа, немедленно расшифровать начало второго сообщения (Т2 = С2 ⊕ Ключ) и увидеть там осмысленное SPRUCHNR, что подтвердило их догадку.

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

«Розеттский камень» криптоанализа: Зачем был нужен всего один ключ?

Но неужели немцы не меняли ключи? Конечно, меняли. Система ключей «Лоренца» была многоуровневой:

* Ключ сообщения: Уникальные начальные положения всех 12 колес. Оператор должен был менять их для каждого нового сообщения. Роковая ошибка немца заключалась в том, что он нарушил это правило.

* Конфигурация машины: Физические настройки штырьков на самих колесах. Менялись гораздо реже, например, раз в месяц.

Поэтому захваченный 4000-символьный ключ был абсолютно бесполезен для чтения других сообщений — у них был бы другой ключ сообщения. Но его ценность была в другом. Он был «Розеттским камнем» — первым и единственным длинным образцом "чистой" работы машины, попавшим в руки союзников. Он был не ключом, который открывает все двери, а инструкцией, как устроен сам замок.

Прорыв Билла Татта: что такое «статистическая уязвимость»?

Этот уникальный 4000-символьный ключ передали математику Биллу Татту. Перед ним была, казалось бы, случайная последовательность символов. Но Татт предположил, что она сгенерирована вращающимися колесами, и начал искать в ней скрытые закономерности.

Его гениальный метод заключался в сравнении этого потока данных с самим собой, но со сдвигом. Он брал последовательность и накладывал на нее ее же копию, сдвинутую на один символ, потом на два, на три и так далее, каждый раз выполняя операцию XOR. В абсолютно случайной последовательности результат такого действия тоже был бы случайным. Но когда Татт сделал сдвиг на 41 позицию, он обнаружил аномалию: результат оказался не совсем случайным. В нем было статистически значимое отклонение от нормы. Это означало, что он нашел "пульс" машины — период одного из ее 12 шифрующих колес.

По сути, он доказал, что ключ, который должен был быть идеально случайным, имел дефект. Эта статистическая уязвимость — отклонение от идеальной случайности — стала ахиллесовой пятой шифра. Изолировав паттерн первого колеса, Татт смог "вычесть" его влияние из общего ключа, что сделало шум от других колес более различимым. За несколько месяцев он, как археолог, по этому "эху" обратным инжинирингом восстановил полную логическую структуру всех 12 колес машины «Лоренц», ни разу ее не видя.

Рождение гиганта: Colossus

Теоретически шифр был взломан. Блетчли-парк теперь знал, как устроена машина. Но чтобы применять эти знания на практике для ежедневной дешифровки, нужно было для каждого нового сообщения быстро находить его уникальный ключ сообщения (те самые начальные положения колес). Эта задача требовала автоматизации сложнейшего статистического анализа. Именно для этого и был построен «Colossus» — первая в мире программируемая электронная цифровая вычислительная машина, созданная инженером Томми Флауэрсом.

Что такое "тестовая последовательность"?

Чтобы понять, что делал «Колосс», нужно знать ключевое открытие Татта: ключ «Лоренца» (K) состоял из двух частей, которые генерировались двумя разными группами колес («хи»-колеса и «пси»-колеса).

K = K_chi ⊕ K_psi

Татт обнаружил, что если "очистить" шифротекст от влияния первой части ключа (K_chi), то результат будет статистически предсказуемым.

Шифротекст ⊕ K_chi = (Текст ⊕ K) ⊕ K_chi = (Текст ⊕ K_chi ⊕ K_psi) ⊕ K_chi = Текст ⊕ K_psi

Получившееся значение (Текст ⊕ K_psi) было уже не таким случайным, как исходный шифр.

Задача «Колосса» состояла в том, чтобы подобрать правильный K_chi. Он не знал полный ключ. "Тестовая последовательность" — это и есть одна из гипотез о том, чему равен K_chi. «Колосс» перебирал все возможные начальные настройки «хи»-колес, генерировал соответствующий K_chi и проверял, делает ли он шифротекст "менее случайным".

Таким образом, его работа выглядела так:

1. Зашифрованное сообщение (C) считывалось с бумажной перфоленты на огромной скорости.

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

3. Машина вычисляла C ⊕ K_chi (Шифротекст ⊕ Тестовая последовательность) и производила статистический анализ результата. Если результат был близок к случайному шуму, «Колосс» отбрасывал эту гипотезу и генерировал следующую "тестовую последовательность". Если же результат анализа показывал отклонение от случайности (ту самую уязвимость, предсказанную Таттом), машина останавливалась. Это означало, что с высокой вероятностью найдены правильные начальные настройки для «хи»-колес.

После того как «Колосс» находил первую часть ключа (K_chi), оставшуюся, более простую часть (K_psi) аналитики вскрывали уже другими, более медленными методами.

«Мозгом» Colossus были около 1500 (а в поздних версиях — до 2500) вакуумных электронных ламп. Это был решающий разрыв с прошлым. Электроны вместо шестеренок. Отсутствие движущихся механических частей для выполнения логики означало, что вычисления происходили со скоростью, близкой к скорости света.

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

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

Американский фронт: Битва за траектории

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

Проблема заключалась в том, что орудий производилось гораздо больше, чем таблиц для стрельбы из них. Для точного поражения цели требовались сложнейшие баллистические расчеты, учитывающие десятки факторов: от направления ветра и плотности воздуха до формы снаряда. Команда людей-вычислителей тратила до 40 часов на расчет одной-единственной траектории. Армия США столкнулась с критическим «математическим отставанием».

Ответом на этот вызов стал проект, профинансированный армией США в Школе электротехники Мура еще в 1943 году. Цель была амбициозной: создать машину, способную решать эти дифференциальные уравнения за минуты, а не за часы.

Воплощение грубой силы: ENIAC

Разработка и постройка машины оказались настолько монументальной задачей, что Вторая мировая война закончилась раньше, чем она была завершена. Так, родившийся из нужд войны, ENIAC (Electronic Numerical Integrator and Computer) был официально представлен миру уже после ее окончания, в феврале 1946 года.

Если «Колосс» был узкоспециализированным гением, то ENIAC был универсальным гигантом. Это был настоящий электронный гигант, монстр из стали, стекла и проводов весом в 30 тонн, в «мозге» которого работали более 17 000 вакуумных ламп, способный выполнять вычисления со скоростью 5000 операций в секунду. И хотя он не успел рассчитать баллистические таблицы для Второй мировой, его первая настоящая задача оказалась еще более зловещей и секретной: еще до официального запуска, в конце 1945 года, на нем были проведены расчеты для проекта водородной бомбы в Лос-Аламосе.

ENIAC был грубой, но необходимой силой. Он доказал, что абстрактная идея Тьюринга об универсальной машине может быть реализована в железе. Однако его «программирование» было кошмаром: для каждой новой задачи инженерам приходилось часами вручную переключать тысячи проводов на коммутационных панелях. Аппаратное обеспечение (hardware) и программное обеспечение (software) все еще были одним запутанным целым.

Так, ENIAC стал не оружием, которое закончило Вторую мировую, а главным вычислительным инструментом, с которого началась Холодная война. Мир получил свой первый электронный компьютер, но теперь перед ним встала новая, не менее сложная задача: как научить его думать без физического вмешательства?

Апогей абстракции: Шеннон, энтропия и призрак черной дыры

Colossus и ENIAC были монументальными достижениями инженерии, но они были ответами, созданными еще до того, как сам вопрос был полностью сформулирован. Что такое «информация»? Можно ли ее измерить? Существуют ли универсальные законы, управляющие ее передачей? Компьютеры уже появились, но у них не было строгой математической теории, описывающей саму суть того, с чем они работали.

Ответ пришел в 1948 году, когда инженер и математик Клод Шеннон опубликовал свою «Математическую теорию связи». Эта работа стала для цифрового мира тем же, чем законы Ньютона — для механики. Шеннон ввел фундаментальное понятие «бит» — минимальной, неделимой единицы информации, выбор между двумя равновероятными возможностями. Но он пошел гораздо дальше. Он ввел понятие информационной энтропии — строгой математической меры неопределенности или «сюрприза», содержащегося в сообщении. Поразительно, но его формула была математически аналогом энтропии в термодинамике; если в физике энтропия измеряет степень беспорядка в системе, то у Шеннона она измеряла степень непредсказуемости в потоке данных.

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

Работа Шеннона стала вершиной «развода» вычислений и физики. Информация окончательно превратилась в чистую, абстрактную математику. Но этот триумф таил в себе пророческое семя будущего воссоединения.

Именно в XX веке некоторые физики, в первую очередь Джон Арчибальд Уилер, начали выдвигать радикальную идею, выраженную в его знаменитом афоризме «it from bit» («всё из бита»). Эта гипотеза предполагает, что в самом фундаменте нашего мира лежит не материя и не энергия, а информация. Что элементарные частицы, поля и само пространство-время — это проявления обработки неких фундаментальных информационных битов.

Нигде эта шокирующая связь информации и космоса не проявилась так драматично, как в спорах о черных дырах. Фундаментальный постулат квантовой механики — унитарность — гласит, что эволюция любой замкнутой системы обратима во времени. Проще говоря, законы физики, описываемые унитарными операторами, гарантируют, что если вы знаете конечное состояние системы, вы всегда можете однозначно восстановить ее прошлое. Информация не может быть уничтожена. Но что происходит с информацией об объекте, который падает в черную дыру?

Стивен Хокинг изначально утверждал, что она исчезает навсегда, нарушая унитарность и вызывая кризис в теоретической физике. Решение начало появляться, когда физики, в первую очередь Яаков Бекенштейн и сам Хокинг, поняли, что у черных дыр есть энтропия. Подобно горячему газу, черная дыра обладает температурой и медленно "испаряется" через излучение Хокинга. Самым поразительным было то, что эта энтропия была пропорциональна не объему черной дыры (кубу ее радиуса), как можно было бы ожидать, а площади ее поверхности — квадрату радиуса. Это был шокирующий намек: вся информация о том, что упало внутрь, может быть как-то закодирована на двумерной поверхности горизонта событий. Сама формула энтропии Бекенштейна-Хокинга оказалась прямым аналогом энтропии Шеннона: она подсчитывала количество информации (в битах), необходимое для полного описания внутреннего состояния черной дыры.

Десятилетия спустя, после ожесточенных дебатов, Хокинг публично признал свою ошибку, согласившись, что информация все-таки должна как-то сохраняться и "утекать" обратно во Вселенную вместе с его излучением. Битва за судьбу одного бита, упавшего в черную дыру, доказала: информация — это не просто инженерное понятие, а фундаментальное свойство реальности, такое же незыблемое, как закон сохранения энергии.

Элегантная архитектура: Фон Нейман и призрак Бэббиджа

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

Решение этой проблемы предложил блестящий математик Джон фон Нейман, но он не начал с чистого листа. Казалось, механические монстры Чарльза Бэббиджа были давно забытым историческим курьезом. Однако фон Нейман знал о его «Аналитической машине». Именно там, в чертежах вековой давности, он нашел недостающий элемент: идею Бэббиджа об отделении «Склада» (памяти) от «Мельницы» (вычислительного устройства) и управления ими с помощью инструкций.

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

Однако эта элегантная архитектура, разделившая вычисления на процессор (CPU) и память (RAM), создала фундаментальное ограничение, которое преследует нас и по сей день. Оно известно как «фон-неймановское узкое место» (von Neumann bottleneck). Суть его в том, что для любого, даже простейшего вычисления, процессору необходимо постоянно «перегонять» инструкции и данные из медленной памяти в свои быстрые регистры и обратно по относительно узкому каналу.

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