Таблица 1. Определение действия некоторых элементарных логических гейтов. Каждая строка показывает два входных значения А и В и соответствующие выходные значения для гейтов AND, OR и XOR. Выход для NOT гейта показан только для входа В.

(возможно большого) булевского выражения, и любое булевское выражение может быть построено из фиксированного набора логических гейтов. Такой набор (например, AND (И), OR (ИЛИ) и NOT (ИЕ)) называется универсальным. В действительности можно обойтись только двумя гейтами, такими как AND и NOT, или OR и NOT. Действуя альтернативным способом, мы можем заменить некоторые из этих примитивных гейтов другими, такими как исключающее ИЛИ (называется OR); тогда AND и XOR образуют универсальный набор. Результаты действия этих гейтов приведены в таблице 1. Любое устройство, которое может смонтировать произвольные комбинации логических гейтов из универсального набора, является универсальным компьютером.

Какие из приведенных выше гейтов обратимы? Поскольку AND, OR и XOR - операции, отображающие много данных в одно, то в том виде, как они заданы, они не являются логически обратимыми. Прежде чем мы обсудим, как эти логические гейты могут быть сделаны обратимыми, мы рассмотрим некоторые нестандартные гейты, которые нам для этого потребуются.

4. FANOUT (разворачивание) и ERASE (стирание)

Хотя приведенные выше гейты достаточны для математического ппарата логики, они недостаточны для построения практической вычислительной машины. Для этого требуются еще гейты FANOUT и ERASE (рис. 2).

Вначале рассмотрим гейт FANOUT. Является ли он обратимым? Очевидно, никакая информация не разрушается, поэтому он, по крайней мере логически, обратим. Ландауэр показал, что он может быть так-

а) FANOUT

Ъ) ERASE

Рис. 2. Два нестандартных гейта, которые, в дополнение к универсальному набору, требуются для построения компьютера: (а) FANOUT гейт, который ублирует входные данные А и (Ь) ERASE гейт, который уничтожает его входные данные.

е и физически обратим [8]. Опишем простую модель для FANOUT,

снованную на схеме Беннетта для обратимого измерения (рис. 3) [9]. Здесь темный шар используется для того, чтобы определить наличие или отсутствие второго (светлого) шара внутри ловушки. Ловушка состоит из набора отражателей и может рассматриваться как регистр с

дним битом памяти. Если ловушка занята, то темный шар отражается и покидает ловушку в направлении М (при этом светлый шар продол-

ает двигаться вдоль своей первоначальной траектории); в противном случае он проходит без помех в направлении N. После того, как темный шар покинет ловушку, направление его движения используется для того, чтобы заселить или нет другую ловушку.

Рис. 3. Обратимое измерение наличия светлого шара в ловушке, состоящей из отражателей (темные прямоугольники) [9]. Темный шар входит в ловушку из Y. В отсутствии светлого шара в ловушке темный шар проследует по пути HN. При наличии светлого шара (в это время начинающего движение в X) темный шар отклонит светлый шар от его первоначальной траектории ABCDEF на траекторию ABGDEF, а сам проследует по пути HIJKLM.

Давайте теперь рассмотрим операцию ERASE, которая требуется для периодической «чистки» памяти компьютера.

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

Рассмотрим одиночный бит, представленный как пара равновероятных классических состояний некоторой частицы. Для стирания информации о состоянии частицы мы должны необратимым образом сжать фазовое пространство в два раза. Если позволить этому сжатому фазовому пространству адиабатически расширяться при температуре Т до его первоначального размера, то можно получить количество работы, равное квТ\п2 (где кв - постоянная Больцмана). Основыва-сь на простых моделях и более общих аргументах относительно сжатия фазового пространства, Ландауэр сделал вывод о том, что стирание одного бита информации при температуре Т требует диссипации по меньшей мере квТ\п2 теплоты (результат, известный как принцип андауэра) [8].

5. Вычисление без ERASE

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

/: а (а, /(а)).

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

Как этот трюк может быть использован для выполнения обратимой огики? Одно решение, известное как Тоффоли-гейт, показано на рис. 4 8, 10, 11]. Выход этого гейта может быть разложен в различные гейты: