Реверсивная логика
Реверсивная логика — логическая система, в которой все операции обратимы.[1]
Решение в рамках методов классических логик невозможно, так как всё упирается в необратимость дизъюнкции.
Рядом современных исследователей предлагались «инженерные» методы, т. н. «реверсивные вычисления».
История вопросаПравить
Одним из первых, кто поднял вопрос и пытался создать реверсивную силлогистическую систему, был философ-исмаилит Хамид ад-Дин аль-Кирмани (X‒XI век):
«если [мы] хотим убедиться, что в определении схвачена истина вещи: обратив определение и увидев, что и обратная его форма истинна, мы знаем, что это и есть искомое определение.
… если при обращении подтвердился начальный смысл, и ничто из него не оказалось ложным, мы обретаем уверенность в его истинности и знаем, что это есть его естественное определение.
… если формулировка не является обращаемой, при присоединении к ней слова „все/всякий“, то она не соответствует (определяемому) и не может браться в качестве его определения. Предположим, мы скажем: „Всякий человек — живое“, а затем задумаемся, действительно ли это — естественное определение человека; тогда мы обратим его: „Всякое живое — человек“ — и увидим, что смысл этой формулировки не соответствует первому изречению, ибо присоединяет к человечности то, что человеком не является: так мы узнаем ложность этого высказывания и не примем его в качестве определения человека.»[2]
Реверсивные вычисленияПравить
В 1973 году Ч. Беннет[3] предложил[4] создать логический реверсивный булев компьютер.
Э. Фредкин[5] и Т. Тоффоли[6] предложили[7] свой оригинальный метод т. н. «бильярдных шаров».[8]
Р. Меркле предложил реализовать модель «бильярдных шаров» на практике.[9] В его интерпретации роль биллиардных шаров играли электроны, а стола — алмазный контейнер, обработанный определенным образом (модель исследовалась при температуре 1 K). Меркле предусмотрел использование управляющих электронов и возможные потери энергии.[10]
Большинство современных исследований по реверсивной вычислимости в качестве физической модели используется именно модель биллиардных шаров Тоффоли-Фредкина.[10]
Вычисления на обратимых автоматахПравить
Для организации цепочки вывода на конечном автомате, предполагается, что автомат считывает входное слово слева направо[11] и переходит из начального[12] состояния, согласно функции переходов. Слово Σ = A1,A2…Bm распознается (принимается) автоматом M, когда существует путь по ребрам графа автомата M c началом пути — во множестве начальных состояний I, и конечным состоянием — во множестве заключительных состояний F.[13]
При определённых условиях, допустимые слова языка Σ, проходящие через состояния K, и фактически разделённые на три языка: Lk(Σ) — входящий (левый) язык состояния k, Cq(Σ) — язык внутреннего цикла состояния k, Rk(Σ) — выходящий (правый) язык состояния k, могут быть заданы (выбраны) так, что автомат М окажется обратимым.
|
— [14]
Для формирования обратимых конечных автоматов может быть привлечён аппарат исчисления секвенций. В случае, когда будет использована субструктурная логическая система[15] с секвенциями исключительно только вида:
А1&A2& … &Аn ⊢ В1&B2& … &Bm,
это будет обратимый конечный автомат.
Динамические системыПравить
Система, в которой последовательность состояний, через которые она проходит, заданная рекуррентной зависимостью вида:
- Ut+1 = α1 (Ut) [1]
представляет собой систему первого порядка. U — состояния системы, α1 — динамический закон системы, то есть функция, которая в качестве аргумента берёт текущее состояние Ut и возвращает следующее состояние Ut+1. В общем случае закон [1] приводит к необратимой динамике. Сам же процесс, описываемый таким законом, называют «марковским».
Система второго порядка, заданная зависимостью вида:
- Ut+1 = α1 (Ut) + α2 (Ut-1) [2]
в которой «следующее» состояние Ut+1 является функцией и «текущего» состояния, и «прошлого» состояния Ut-1, использует для определения дальнейшей траектории пару последовательных состояний. В общем случае зависимости второго порядка («процесс Юла») приводят также к необратимой динамике, но существуют зависимости второго порядка специального вида, которые гарантируют обратимость динамики для любого произвольного процесса:
- Ut-1 = α (Ut, Ut+1) [3]
когда пары последовательных состояний достаточно также для однозначного определения также и обратной траектории..[16]
Система, заданная продукциями вида [3] будет обратима, если и только если она устанавливает взаимно-однозначные соответствия между всеми старыми и новыми состояниями рассматриваемого процесса. Для бинарных процессов такая система может быть определена над девятнадцатибуквенном алфавитом, заданном графом де Брёйна B(n=3, k=2).
См. такжеПравить
СсылкиПравить
- ↑ А. Н. Непейвода. Реверсивные конструктивные логики
- ↑ Хамид ад-Дин аль-Кирмани. Успокоение разума. с. 115. Пер. А. В. Смирнова. — М.: «Ладомир», 1994. — 510 с. ISBN 5-86218-114-8
- ↑ en:Charles H. Bennett (computer scientist)
- ↑ C. H. Bennett, Logical reversibility of computation, IBM Journal of Research and Development, vol. 17, no. 6, pp. 525‒532, 1973.
- ↑ en:Edward Fredkin
- ↑ en:Tommaso Toffoli
- ↑ E. Fredkin and T. Toffoli. Conservative logic. International Journal of Theoretical Physics, 1982.
- ↑ en:Billiard-ball computer
- ↑ Ralph C. Merkle. Towards Practical Reversible Logic, in Workshop on Physics and Computation, PhysComp ’92, October, Dallas Texas; IEEE press 1992.
- ↑ а б А. Н. Непейвода. Реверсивные вычисления: Обзор мирового опыта
- ↑ либо справа налево, тогда изменится соответствующее разделение нижеуказанных языков
- ↑ или текущего
- ↑ Н. И. Крайнюков. Обратимые конечные автоматы и условия вложения полугруппы в группу
- ↑ В. А. Орлов, В. А. Конявский. Общеавтоматное шифрование.
- ↑ en:Substructural logic
- ↑ Т.Тоффоли, Н. Марголус «Машины клеточных автоматов» — М.: Мир, 1991. — 280 с. ISBN 5-03-001619-8