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

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

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

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

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

История вопроса[править]

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

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

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

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

Реверсивные вычисления[править]

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

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

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

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

Динамические системы[править]

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

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]

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

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

См. также[править]

Ссылки[править]

  1. А. Н. Непейвода. Реверсивные конструктивные логики
  2. Хамид ад-Дин аль-Кирмани. Успокоение разума. с. 115. Пер. А. В. Смирнова. — М.: «Ладомир», 1994. — 510 с. ISBN 5-86218-114-8
  3. en:Charles H. Bennett (computer scientist)
  4. C. H. Bennett, Logical reversibility of computation, IBM Journal of Research and Development, vol. 17, no. 6, pp. 525‒532, 1973.
  5. en:Edward Fredkin
  6. en:Tommaso Toffoli
  7. E. Fredkin and T. Toffoli. Conservative logic. International Journal of Theoretical Physics, 1982.
  8. en:Billiard-ball computer
  9. Ralph C. Merkle. Towards Practical Reversible Logic, in Workshop on Physics and Computation, PhysComp ’92, October, Dallas Texas; IEEE press 1992.
  10. а б А. Н. Непейвода. Реверсивные вычисления: Обзор мирового опыта
  11. Т.Тоффоли, Н. Марголус «Машины клеточных автоматов» — М.: Мир, 1991. — 280 с. ISBN 5-03-001619-8


Черновик
Исправьте и дополните до полноценной статьи Русской Энциклопедии.