1

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

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

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

1 ответ 1

4
+50

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

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

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

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

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

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

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