Оборотні обчислення
Оборотні обчислення(англ. Reversible computing ) - Модель обчислень, в якій процес обчислення є деякою мірою оборотним. Наприклад, у обчислювальній моделі, що використовує набори станів і переходів між ними, необхідною умовою оборотності обчислень є можливість побудови однозначного (ін'єктивного) відображення кожного стану наступного за ним. На XX століття та початок XXI століття оборотні обчислення зазвичай відносять до нетрадиційних моделей обчислень.
Зміст
Існує два основних типи оборотності обчислень:фізично оборотніілогічно оборотні. [1]
Процес фізично звернемо, якщо після його завершення система не збільшила свою фізичну ентропію, тобто процес є ізоентропійним. Фізично оборотні схеми: charge-recovery logic (зберігаюча заряд логіка), адіабатичні схеми, адіабатичні обчислення. Насправді нестаціонарний фізичний процес може бути повністю фізично оборотним (изоэнтропийным), проте добре ізольованих систем можливе наближення до повної оборотності.
Ймовірно, найбільшим стимулом вивчення технологій для реалізації оборотних обчислень є те, що вони є єдиним способом покращити енергоефективність обчислень за фундаментальні межі, передбачені принципом Неймана — Ландауера [2] [3] , згідно з яким виділяється принаймніkTln(2) теплоти (близько 3×10 −21 Дж при T=300K) на кожну незворотну операцію над бітом (при стиранні інформації). На початок XXI століття комп'ютери розсіювали приблизно в мільйон разів більше тепла, на початок 2010-х різниця знизилася до кількох тисяч [4] .
Як було показано Рольфом Ландауером (англ.) з IBM в 1961 [3] , для того, щоб процес обчисленьбув фізично оборотним, потрібно, щоб він також був логічно оборотним (logically reversible). У принципі Ландауера їм уперше було сформульовано правило, згідно з яким стиранняNбіт невідомої інформації завжди пов'язане зі збільшенням термодинамічної ентропії на величину принаймні рівнуNkln(2). Дискретний детермінований процес обчислень називається логічно оборотним у разі, якщо функція переходів, що відображає старий стан системи в новий є ін'єктивною (кожному новому стану однозначно відповідає один старий стан), тобто, за інформацією про кінцевий логічний стан схеми, можливо визначити вхідний логічний стан схеми.
Для недетермінованих (імовірнісних або випадкових) процесів фізична оборотність може досягатися при менш суворих обмеженнях, а саме, за умови незменшення сукупності всіх можливих початкових станів (у середньому) у процесі обчислення.
Один із перших варіантів [5] реалізації оборотних обчислень був запропонований у роботах Чарльза Беннетта (англ.) українців. , [6] [7] (IBM Research, 1973). В даний час безліч учених запропоновано десятки концепцій оборотних обчислень, включаючи оборотні логічні вентилі, електронні схеми, архітектури процесорів, мови програмування, алгоритми [8] [9] .
Для реалізацій оборотних обчислювальних схем та оцінок їх складності та обмежень використовується формалізація через оборотні вентилі – аналоги логічних вентилів. Наприклад, вентиль інвертора NOT (НЕ) є оборотним, оскільки зберігає інформацію. У той же час логічний вентиль виняткове АБО (XOR) є незворотним - значення його входів не можуть бути відновлені з єдиного вихідного значення. Оборотним аналогом XOR може стативентиль керованого заперечення (CNOT - controlled NOT).