Реверсивная логика

Реверсивная логика — логическая система, в которой все операции обратимы.

Решение в рамках методов классических логик невозможно, так как всё упирается в необратимость дизъюнкции.

Рядом современных исследователей предлагались «инженерные» методы, т. н. «реверсивные вычисления».

История вопроса

Одним из первых, кто поднял вопрос и пытался создать реверсивную силлогистическую систему, был философ-исмаилит Хамид ад-Дин аль-Кирмани (X‒XI век):

«если [мы] хотим убедиться, что в определении схвачена истина вещи: обратив определение и увидев, что и обратная его форма истинна, мы знаем, что это и есть искомое определение.

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

… если формулировка не является обращаемой, при присоединении к ней слова „все/всякий“, то она не соответствует (определяемому) и не может браться в качестве его определения. Предположим, мы скажем: „Всякий человек — живое“, а затем задумаемся, действительно ли это — естественное определение человека; тогда мы обратим его: „Всякое живое — человек“ — и увидим, что смысл этой формулировки не соответствует первому изречению, ибо присоединяет к человечности то, что человеком не является: так мы узнаем ложность этого высказывания и не примем его в качестве определения человека.»

Реверсивные вычисления

В 1973 году Ч. Беннет предложил создать логический реверсивный булев компьютер.

Э. Фредкин и Т. Тоффоли предложили свой оригинальный метод т. н. «бильярдных шаров».

Р. Меркле предложил реализовать модель «бильярдных шаров» на практике. В его интерпретации роль биллиардных шаров играли электроны, а стола — алмазный контейнер, обработанный определенным образом (модель исследовалась при температуре 1 K). Меркле предусмотрел использование управляющих электронов и возможные потери энергии.

Большинство современных исследований по реверсивной вычислимости в качестве физической модели используется именно модель биллиардных шаров Тоффоли-Фредкина.

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

Для организации цепочки вывода на конечном автомате, предполагается, что автомат считывает входное слово слева направо и переходит из начального состояния, согласно функции переходов. Слово Σ = A1,A2…Bm распознается (принимается) автоматом M, когда существует путь по ребрам графа автомата M c началом пути — во множестве начальных состояний I, и конечным состоянием — во множестве заключительных состояний F.

При определённых условиях, допустимые слова языка Σ, проходящие через состояния K, и фактически разделённые на три языка: Lk(Σ) — входящий (левый) язык состояния k, Cq(Σ) — язык внутреннего цикла состояния k, Rk(Σ) — выходящий (правый) язык состояния k, могут быть заданы (выбраны) так, что автомат М окажется обратимым.

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

—

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

А1&A2& … &Аn ⊢ В1&B2& … &Bm,

это будет обратимый конечный автомат.

Динамические системы

Система, в которой последовательность состояний, через которые она проходит, заданная рекуррентной зависимостью вида:

U_t+1 = α₁ (U_t) [1]

представляет собой систему первого порядка. U — состояния системы, α₁ — динамический закон системы, то есть функция, которая в качестве аргумента берёт текущее состояние U_t и возвращает следующее состояние U_t+1. В общем случае закон [1] приводит к необратимой динамике. Сам же процесс, описываемый таким законом, называют «марковским».

Система второго порядка, заданная зависимостью вида:

U_t+1 = α₁ (U_t) + α₂ (U_t-1) [2]

в которой «следующее» состояние U_t+1 является функцией и «текущего» состояния, и «прошлого» состояния U_t-1, использует для определения дальнейшей траектории пару последовательных состояний. В общем случае зависимости второго порядка («процесс Юла») приводят также к необратимой динамике, но существуют зависимости второго порядка специального вида, которые гарантируют обратимость динамики для любого произвольного процесса:

U_t-1 = α (U_t, U_t+1) [3]

когда пары последовательных состояний достаточно также для однозначного определения также и обратной траектории..

Система, заданная продукциями вида [3] будет обратима, если и только если она устанавливает взаимно-однозначные соответствия между всеми старыми и новыми состояниями рассматриваемого процесса. Для бинарных процессов такая система может быть определена над девятнадцатибуквенном алфавитом, заданном графом де Брёйна B(n=3, k=2).

См. также

• en:Reversible computing
• Шарль Г. Бенне, Рольф Ландауэр. Физические пределы вычислений ^✡