1

Что значит "обратимая логическая операция"?

В чем ее преимущество в сравнении с другими? В каких областях применение обратимых логических операций проявляется больше всего?

1
  • 2
    Скопировал Ваш заголовок, без изменений задал вопрос Google. Он, оказывается, знает! Или нужно что-то другое? Тогда желательно уточнить сам вопрос. 23 ноя 2017 в 23:53

1 ответ 1

4
+50

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

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

Идея обратимых вычислений: если в качестве элементарных логических операций допускать только обратимые операции, то в принципе можно проводить вычисления вообще без затрат энергии (т.е., проводить вычисления со сколь угодно малыми затратами энергии). Обратимые логические операции действительно существуют. Например, !x (отрицание) или x^y (искл. или). Последний, вообще говоря, не обратим, см. документ по ссылке ниже.

Есть универсальные обратимые логические операции - "гейт Тоффоли": x = x ^ (y & z).

Любое сколь угодно сложное обратимое вычисление можно представить в виде цепочки гейтов Тоффоли. Также обратимые логические гейты описаны здесь в разделе 6.3.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.