Традиция

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

Реверсивная логика — логическая система, в которой все операции обратимы.[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, могут быть заданы (выбраны) так, что автомат М окажется обратимым.

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

— [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).

См. такжеПравить

СсылкиПравить

  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. ↑ либо справа налево, тогда изменится соответствующее разделение нижеуказанных языков
  12. ↑ или текущего
  13. ↑ Н. И. Крайнюков. Обратимые конечные автоматы и условия вложения полугруппы в группу
  14. ↑ В. А. Орлов, В. А. Конявский. Общеавтоматное шифрование.
  15. ↑ en:Substructural logic
  16. ↑ Т.Тоффоли, Н. Марголус «Машины клеточных автоматов» — М.: Мир, 1991. — 280 с. ISBN 5-03-001619-8


Источник — https://traditio.wiki/w/index.php?title=Реверсивная_логика&oldid=697163