Сейчас мы опишем три обратимых примитивных элемента, которые могут быть использованы для создания универсальной машины (Тоффоли (Toffoli) [4]). Первый из них – это NOT, который, очевидно, не теряет информации и является обратимым, обращение достигается повторным действием NOT. Так как принятый символ не симметричен, вместо него мы будем использовать $X$ на проводе (см. рис. За).

Следующим является элемент, который мы будем называть CONTROLLED NOT (контролируемый нет) (см. рис. $3 \mathrm{~b}$ ). Здесь имеются две входящие линии $a$ и $b$ и две выходящие – $a^{\prime}$ и $b^{\prime}$. Линия $a^{\prime}-$
Рис. 3. Обратимые примитивные элементы

всегда та же самое, что и $a$, которая служит контрольной линией. Если контрольная линия активирована ( $a=1$ ), тогда выход $b^{\prime}$ есть NOT от $b$. В противном случае (как вы видите, я не профессиональный программист, он бы сказал «иначе» («else»)) $b$ не меняется: $b^{\prime}=b$. Таблица значений для входа и выхода приведена на рис. 3. Действие обращается простым своим повторением. Величина $b^{\prime}$ на самом деле является симметричной функцией $a$ и $b$, которая называется XOR (исключающее или), $a$ или $b$, но не оба. Эта операция подобна суммированию $a$ и $b$ по модулю 2. Она может быть использована для сравнения $a$ и $b$, давая 1 как сигнал того, что они различны. Пожалуйста, заметьте, что эта функция XOR сама по себе не является обратимой. Например, если получится значение 0 , мы не можем сказать, получилось ли оно от $(a, b)=(0,0)$ или от $(1,1)$, но мы сохраняем другую линию $a^{\prime}=a$ для устранения неоднозначности.

Мы будем представлять CONTROLLED NOT, помещая 0 на контрольную линию, связанную вертикальной линией с $X$ на проводе, который контролируется.
Данный элемент может также обеспечить нас операцией FANOUT, так как, если $b=0$, мы видим, что $a$ копируется на линию $b^{\prime}$. Эта функция COPY будет важна позднее. Этот элемент также обеспечивает нас операциеи EXCHANGE, так как три таких элемента, примененных последовательно на паре линий, но с чередующимся выбором контрольной линии, совершают обмен информации на линиях (рис. $3 \mathrm{~b}$ ).

Оказывается, что комбинации только этих двух элементов недостаточны для выполнения произвольных логических функций. Необходим некоторый элемент, включающий три линии. Мы выбрали тот, который можно назвать CONTROLLED CONTROLLED NOT (контролируемый контролируемый нет). Здесь (см. рис. 3c) у нас есть две контрольные линии $a, b$, которые остаются неизменными на выходе и которые изменяют третью линию $c$ на NOT $c$, только если обе линии активированы $\left(a=1\right.$ и $b=1$ ). В противном случае $c^{\prime}=c$. Если на входе третьей линии установлен 0 , то, очевидно, $c^{\prime}=1$, только если $a=1$ и $b=1$, тем самым мы получаем функцию AND (см. таблицу 1).

Три комбинации для $(a, b)$, а именно, $(0,0),(0,1)$ и $(1,0)$, все приводят к одному и тому же значению 0 функции $\operatorname{AND}(a, b)$, следовательно, для устранения неоднозначности требуется два бита. Они сохраняются на линиях $a, b$ на выходе, поэтому эта функция может быть обращена (повторным действием ее самой). Функция AND является переносчиком бита для суммы $a$ и $b$.

Известно, что из комбинации этих элементов может быть составлена любая логическая схема, а в действительности и показано, что может быть сделан универсальный компьютер. Мы проиллюстрируем это небольшим примером. Во-первых, конечно, как вы видите на рис. 4, мы можем сделать сумматор, используя последовательно сначала CONTROLLED CONTROLLED NOT, а затем CONTROLLED NOT. Тогда из $a, b$ и 0 на входящих линиях получатся первоначальное $a$ на одной линии, сумма на второй и перенос на третьей.

Более сложная схема – полный сумматор (см. рис. 5), который берет перенос $c$ (от некоторого предыдущего суммирования) и складывает его с двумя линиями $a$ и $b$, а кроме того, содержит дополнительную линию $d$ с 0 на входе. Эта схема требует составления

Рис. 4. Сумматор вместе четырех примитивных элементов. Помимо полной суммы трех линий $a, b$ и $c$ и переноса, мы получаем еще два сообщения на двух других линиях. Одним из них является $a$, с которого мы начинали, а другое – это некоторая промежуточная величина, которую мы вычислили по дороге.
Рис. 5. Полный сумматор
Это типично для таких обратимых систем; они производят не только то, что вы хотите получить на выходе, но и определенное количество мусора. В этом конкретном случае и, как оказывается, во всех случаях в действительности мусор может быть сведен в точности к тому, что имеется на входе, если бы только мы добавили дополнительное CONTROLLED NOT на первые две линии, как показано пунктирными линиями на рис. 5; мы видим, что мусор стал бы $a$ и $b$, что является входом по меньшей мере двух линий. (Мы знаем, что эта схема может быть упрощена, но мы делаем ее такой для иллюстративных целей.)
Таким образом, путем различных комбинаций мы можем создать самый общий логический блок, который преобразует $n$ битов в $n$ битов обратимым образом. Если задача, которую мы пытаемся решить, сама по себе обратима, тогда может не быть дополнительного мусоpa, но в общем случае необходимы некоторые дополнительные линии для сохранения информации, которая вам потребуется для того, чтобы иметь возможность обратить операцию. Другими словами, мы можем получить значения любой функции, что может обычная система, плюс мусор. Мусор содержит информацию, необходимую для обращения процесса.

А каково количество мусора? В общем случае оказывается, что, если искомые выходные данные содержат $k$ битов, то, начав с некоторых входных данных и $k$ битов, содержащих 0 , мы можем получить в качестве результата только входную и выходную информацию, и никакого мусора. Эта процедура обратима, потому, что знание выходной и входной информации позволяет, разумеется, аннулировать все проделанные действия. Это дело всегда обратимо. Аргумент в пользу этого приведен на рис. 6 .

Предположим, что мы начинаем с некоторой машины $M$, которая, начав с входной информации и некоторого большого количества нулей, производит желаемый выход плюс определенное количество дополнительной информации, которую мы называем мусором. Теперь мы видим, что возможна операция копирования, которая может быть проделана последовательностью CONTROLLED NOT, поэтому, если первоначально у нас есть пустой регистр с $k$ битами для выходной информации, мы можем после действия процессора $M$ скопировать выходную информацию из $M$ на этот новый регистр. После этого мы можем построить обратимую машину $M$ наоборот, которая возьмет эту выходную информацию от $M$ и мусор и переведет их во входную информацию и нули. Таким образом, все это, рассматриваемое как общая машина, начинает с $k$ нулей регистра для выходной информации и входных данных, а получает в конце в качестве результата эти $k$ нулей, занятые выходной информацией, и повторение входных данных. Это число нулей, которое первоначально необходимо в $M$ машине для сохранения мусора, восстанавливается опять к нулям и может рассматриваться как внутренние соединения внутри новой полной машины ( $M, \bar{M}$ и ко-
Рис. 6. Уборка мусора

пирование). Итак, мы завершили то, что намеревались сделать, и мусор никогда не должен быть чем-то большим, чем повторение входных данных.