Привет, Вы узнаете о том , что такое обратимые вычисления, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое обратимые вычисления, коллективная логика, reversible computing, физически обратимые вычисления, логически обратимые вычисления, циклическая логика , настоятельно рекомендую прочитать все из категории Квантовая информатика.

обратимые вычисления (англ. Reversible computing) — модель вычислений, в которой процесс вычисления является в некоторой степени обратимым. Например, в вычислительной модели, использующей наборы состояний и переходов между ними, необходимым условием обратимости вычислений является возможность построения однозначного (инъективного) отображения каждого состояния в следующее за ним. На XX век и начало XXI века обратимые вычисления обычно относят к нетрадиционным моделям вычислений.

Обратимость

Существует два основных типа обратимости вычислений: физически обратимые и логически обратимые.

Процесс физически обратим, если по его завершению система не увеличила свою физическую энтропию, то есть процесс является изоэнтропийным. Физически обратимые схемы: charge-recovery logic (сохраняющая заряд логика), адиабатические схемы, адиабатические вычисления. На практике нестационарный физический процесс не может быть полностью физически обратимым (изоэнтропийным), однако для хорошо изолированных систем возможно приближение к полной обратимости.

Вероятно, наибольшим стимулом изучения технологий для реализации обратимых вычислений является то, что они представляются единственным способом улучшить энергоэффективность вычислений за фундаментальные пределы, предсказанные принципом Неймана — Ландауэра , согласно которому выделяется по крайней мере kT ln(2) теплоты (около 3×10⁻²¹ Дж при T=300K) на каждую необратимую операцию над битом (при стирании бита информации). На начало XXI века компьютеры рассеивали примерно в миллион раз больше тепла, на начало 2010-х разница снизилась до нескольких тысяч .

Отношение к термодинамике

Как было показано Рольфом Ландауэром (англ.) из IBM в 1961 году , для того, чтобы процесс вычислений был физически обратимым, требуется, чтобы он также был логически обратимым (logically reversible). В принципе Ландауэра им впервые было сформулировано правило, согласно которому стирание N бит неизвестной информации всегда связано с увеличением термодинамической энтропии на величину по крайней мере равную Nk ln(2). Дискретный детерминированный процесс вычислений называется логически обратимым в случае, если функция переходов, отображающая старое состояние системы в новое является инъективной (каждому новому состоянию однозначно соответствует одно старое состояние), то есть, по информации о конечном логическом состоянии схемы возможно определить входное логическое состояние схемы.

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

Физическая обратимость

Один из первых вариантов реализации обратимых вычислений был предложен в работах Чарльза Беннетта (англ.)русск., (IBM Research, 1973). В настоящее время множеством ученых предложены десятки концепций обратимых вычислений, включая обратимые логические вентили, электронные схемы, архитектуры процессоров, языки программирования, алгоритмы .

Логическая обратимость

Для реализаций обратимых вычислительных схем и оценок их сложности и ограничений используется формализация через обратимые вентили — аналоги логических вентилей. Например, вентиль инвертора NOT (НЕ) является обратимым, так как сохраняет информацию. В то же время логический вентиль исключительное ИЛИ (XOR) является необратимым — значения его входов не могут быть восстановлены из единственного выходного значения. Обратимым аналогом XOR может стать вентиль управляемого отрицания (CNOT — controlled NOT).

Применение обратимых вычислений

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

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

Нэйшин для ее описания использует набор из трех элементов, обозначаемых символами R,P,S, которые соответствуют первым буквам английских слов для камня, ножниц и бумаги. Игра «камень, ножницы, бумага» (о ней тут тоже писали и не раз) известна и на Гавайях как «дзян-кэн». По правилам игры один из трех предметов побеждает другой исходя из циклического набора предпочтений. Это обычно изображается на круговой диаграмме, но можно записать и в строчку:

S < — R < — P < — S

Математический символ отношения «предшествует» (Unicode 227A) использованный на картинке отсутствует во многих шрифтах, поэтому в тексте он заменен на < —

Как это связано с логикой? Известно, что если приравнять ЛОЖЬ=0, ИСТИНА=1, то «И» соответствует функции «минимум», а «ИЛИ» – «максимум». Тот же прием применяют в многозначной и нечеткой логике, так как при таком определении автоматически выполняются многие свойства обычной логики. Так что, задание отношений между элементами определяет аналоги логических операций. Правда, при циклическом наборе предпочтений между тремя элементами некоторыми свойствами приходится пожертвовать. Что поделать, иная логика.

Таблица для аналога «ИЛИ» при таком подходе выглядит как

Таблица для операции «И» стоится аналогично

Попробуем представить обратимый аналог обычного вентиля «ИЛИ». Об этом говорит сайт https://intellect.icu . Предположим, что у него два входа (и два выхода, раз уж он должен быть обратимым), на входы подаются двоичные значения, а один из выходов должен выдать результат операции «ИЛИ». Получается, что одно и то же значение 1 (ИСТИНА) на этом выходе может получиться при трех разных комбинациях на входе: 11, 01, 10. Если бы второй выход мог иметь три разных значения, это можно было бы использовать для обращения такого вентиля.

Так что, уже достаточно простые оценки приводят к идее использовать троичную систему хотя бы на одном выходе. А что если попробовать работать с тремя значения на всех входах и выходах – можно ли получить обратимый вентиль, если использовать троичную логику?

Достаточно распространенной является троичная логика Лукасевича. Она может быть построена и уже упомянутым выше трюком с максимум и минимумом, если предположить, что третьему значению соответствует какое-нибудь число x, 0 < x < 1, например x = 1/2. Получаются хорошо известные троичные таблицы, для «ИЛИ»:

Для «И»:

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

Действительно, на вход можно подать девять возможных пар значений
00 01 0x 10 11 1x x0 x1 xx

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

То есть, три нуля, три единицы, три икса. А вместо этого в таблице для троичного «ИЛИ» стоит только один ноль и пять единиц. Во второй таблице для «И» наоборот, пять нулей и одна единица, что тоже не подходит.

Поэтому, хотя обратимые троичные вентили по отдельности и троичная логика по отдельности достаточно широко используются, вместе их трудно свести. Тут и приходит на помощь «инопланетная» логика. Для наглядности заменим R,P,S на 0,1,$.



Вот таблица для «ИЛИ»

Для значений 0, 1 оно совпадает с обычным «ИЛИ», но при этом обладает уже упомянутым свойством, необходимым для создания обратимого троичного вентиля (каждое значение встречается по три раза). Ситуация с таблицей для операции «И» аналогична

Теперь, чтобы построить полный вариант обратимых троичных вентилей надо еще подобрать таблицу для второго, вспомогательного выхода. В обычной арифметике для обращения функции max(a,b) на втором выходе можно было бы использовать b–a. Нечто похожее можно использовать и в нашем примере

Подошло – вот так будет выглядеть полный троичный обратимый вентиль «ИЛИ»

Видно, что каждая из девяти возможных комбинаций встречается на выходе по одному разу, так что операция обратима. Действие этого вентиля можно еще описать следующим образом: он не изменяет пары 00, 0$, переставляя по циклу семь пар (01, 11, 10, 1$, $1, $$, $0)

Так что, семикратное применение вентиля оставит любую пару значений без изменений, а обратная операция соответствует применению шести вентилей подряд. С вентилями Тоффоли и Фредкина проще, каждый из них совпадает со своим обратным.

Если подавать на вход только значения ноль и единица, то этот троичный вентиль реализует обычную логическую операцию «ИЛИ». Установив единицу на второй вход можно использовать второй выход как операцию «НЕ» от первого входа. Помимо этого, вентиль реализует операцию «разветвления» двоичного значения поданного на второй вход, если на первый подать ноль. Так что этот обратимый троичный вентиль является универсальным для работы с двоичными данными.

Пример обратимого троичного вентиля «И» аналогичен

Этот вентиль не изменяет пары 00 и 01, переставляя по циклу пары
(0$, $$, $0, $1, 1$, 11, 10, 0$)

Он тоже универсален для двоичных операций, но в отличие от «ИЛИ», одного такого вентиля не достаточно для «разветвления». Правда, выбор операции на втором выходе был достаточно произволен. Операция же на первом входе однозначно определяются выбором трех условий: (1) выполнять нужную логическую операцию для двоичных данных, (2) соответсвовать одному из значений на входе, (3) не зависеть от их перестановки.

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

коллективная логика и «невозможные стрелки»

При добавлении еще ящерицы и Спока можно применить ту же идею, что и при расширении двоичной логики до системы из трех элементов и исходя из имеющейся проблемы с пятью повторениями в таблице для троичной логики Лукасевича (0, 1, x), нужно добавить еще два элемента ($ и @). Другой аргумент в пользу пяти значений связан с использованием аналога разности b-a для обращения максимума и минимума: разница между тремя целыми значениями от 0 до 2 может принимать пять разных значений от -2 до 2.

Соотношения между элементами можно опять изобразить на круговой диаграмме или записать в строчку
0 <- 1 <- $ <- x <- @ <- 0 <- x <- 1 <- @ <- $ <- 0

Соответствующая игра тоже известна. Например, ее версия была показана в сериале «Теория Большого взрыва» (картинка с объяснением). Соответствия можно выбрать такие: 0 -камень, 1 – бумага, $ — ножницы, @ — ящерица, x — Спок (уроженец планеты Вулкан в сериале «Звездый путь»).

Рисунок По часовой стрелке с верхнего: ножницы, бумага, камень, ящерица, Спок

Можно продолжать и дальше; для построения похожих круговых диаграмм, особенно хорошо подходят наборы, в которых количество элементов равно простому числу.

Отметим, что циклическая логика (коллективная) не такая уж «инопланетная». Один из наиболее характерных примеров связан с парадоксами Кондорсе и Эрроу относящимися к проблеме выбора. Типичное описание «парадокса голосования» можно найти в книге лауреата Нобелевской премии по экономике Кеннета Эрроу «Коллективный выбор и индивидуальные ценности».

Рассмотрим выбор из трех альтернатив (например, выборы с тремя кандидатами) A, B, C. При этом, каждый голосующий имеет некую упорядоченную систему предпочтений. То есть, если первая альтернатива предпочтительнее второй, а вторая предпочтительная третьей, то первая тоже предпочтительнее третьей. Пример проблем с выбором, возникающий при нарушении этого критерия, тоже описан далее.

Такие упорядоченные предпочтения являются примером транзитивных отношений, а операции с аналогичным свойством ассоциативны, то есть, не зависят от расстановки скобок. Обсуждаемое ранее определение операции «ИЛИ» через задание отношений элементов хорошо согласуется с идеей выбора: операция «А ИЛИ В» – просто выбор между A и B, исходя из некого набора предпочтений (включая случай «А ИЛИ A», который, хотя и затруднительно назвать «выбором», тоже имеет вполне определенный результат, A).

Пусть кто-то полагает, что B лучше A, C лучше В (и по приведенному ранее критерию, C лучше A). Запишем этот выбор как
(1) A < B < C
Предположим, что имеются два других упорядоченных набора предпочтений
(2) B < C < A
(3) C < A < B
Обозначим доли избирателей с соответствующим набором предпочтений как P1, P2, P3. Тогда доля, считающих, что B лучше A будет P1+P3, а полагающих, что C лучше B будет P1+P2, но при этом P2+P3 думают, что A лучше C.

Если все значения P1+P2, P2+P3, P1+P3 больше половины (или, что то же самое, любая доля P1, P2, P3 меньше половины), то при голосовании B побеждает A, C побеждает B, но A побеждает C. Образуется циклическая система коллективных предпочтений, которые во избежание недоразумений обозначим уже используемым значком для отношения без свойства транзитивности
A < — B < — C < — A.

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

Схема 1
Первый тур: выбор между A и B, побеждает B
Второй тур: выбор между B (победившем в первом этапе) и C,
побеждает C (во втором туре и в выборах)

Схема 2
Первый тур: выбор между B и C, побеждает C
Второй тур: выбор между C и A, в выборах побеждает A

Схема 3
Первый тур: выбор между A и C, побеждает A
Второй тур: выбор между B и A, в выборах побеждает B

Эту же проблему можно проиллюстрировать как отсутствие ассоциативности в циклической системе предпочтений. Обозначим операцию выбора как ||

Тогда первые две схемы соответствуют расстановке скобок

((A || B) || C) = B || C = C,
(A || (B || C)) = A || C = A

Вау!! 😲 Ты еще не читал? Это зря!

• Обратимость
• Вентиль Тоффоли
• Вентиль Фредкина
• Квантовый компьютер (квантовая часть вычислений должна быть обратима вплоть до момента измерения)
• Бильярдный компьютер
• Обратимый клеточный автомат
• нечеткая логика
• троичная логика

Исследование, описанное в статье про обратимые вычисления, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое обратимые вычисления, коллективная логика, reversible computing, физически обратимые вычисления, логически обратимые вычисления, циклическая логика и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Квантовая информатика