Беннетт предложил идею создания обратимых гейтов машины Тьюринга.

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

 

Необратимые вычисления

 — дополнительная сохраняемая информация для обращения вычислений («мусор»).

 

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

 

Обратимые вычисления  

В итоге в конце работы остаются только выходные (копированные) и входные начальные данные.

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

 

            Примеры обратимых гейтов машины Тьюринга были приведены Фейнманом (см. рис.). Как уже указывалось выше NOTявляется обратимой логической операцией. Ниже приведена также схема логически обратимого универсального трех-входового гейта Тоффоли (CONTROLLEDCONTROLLEDNOT– дважды контролиремое нет).

 


Ссылка на основную публикацию
Adblock detector