Что значит "обратимая логическая операция"?
В чем ее преимущество в сравнении с другими? В каких областях применение обратимых логических операций проявляется больше всего?
Что значит "обратимая логическая операция"?
В чем ее преимущество в сравнении с другими? В каких областях применение обратимых логических операций проявляется больше всего?
Логические операции, лежащие в основе работы компьютеров, с физической точки зрения являются необратимыми процессами, т.е. они неизбежно сопровождаются ростом энтропии, следовательно, при выполнении этих операций неизбежно происходит рассеяние энергии.
Эта необратимость заключается в том, что при выполнении некоторых операций происходит потеря информации. Например, операция И: x = x & y
. После выполнения этой операции прежнее значение переменной x
в общем случае не восстановить, информация теряется.
Идея обратимых вычислений: если в качестве элементарных логических операций допускать только обратимые операции, то в принципе можно проводить вычисления вообще без затрат энергии (т.е., проводить вычисления со сколь угодно малыми затратами энергии). Обратимые логические операции действительно существуют. Например, !x
(отрицание) или x^y
(искл. или). Последний, вообще говоря, не обратим, см. документ по ссылке ниже.
Есть универсальные обратимые логические операции - "гейт Тоффоли": x = x ^ (y & z)
.
Любое сколь угодно сложное обратимое вычисление можно представить в виде цепочки гейтов Тоффоли. Также обратимые логические гейты описаны здесь в разделе 6.3.