align="justify">. Нехай вхідні змінні - це . Допоміжні змінні схеми й біти результату - це ; в оборотної схемою зіставимо їм додаткові біти, що мають у початковому стані значення 0.
Кожна присвоювання у схемі має вигляд , , . У оборотною схемою аналогом присвоювання буде дію перестановки , , тобто .
Оскільки початкові значення додаткових змінних були рівні 0, їх кінцеві значення будуть такими ж, як і в булевої схемою.
Залишилось поміняти місцями біти, щоб отримати вказаний в умові формат відповіді.
Весь процес обчислення зручно представити наступною схемою (над прямокутниками підписано кількість бітів, всередині - їх вміст):
В
Лемма 6.2. (Очищення сміття). В умовах леми можна провести обчислення функції оборотною схемою розміру (з використанням додаткових бітів).
Доказ. Для очищення сміття буде використана оборотність. Зобразимо процес обчислення схемою, аналогічною тій, що наведена в доказі леми 6.1.
В
Зауваження 6.4. Оборотними обчисленнями зацікавилися при спробі відповісти на питання, яка енергія необхідна для обчислень (класичних). Аналіз показав, що втрати енергії можна спрямувати до нуля для всіх обчислювальних операцій, крім незворотних. Коли проводиться необоротна операція (наприклад, стирання біта), два різних логічних значення ( і ) стають однаковими ( ). Проте фізичні закони на мікрорівні є оборотними, тому відміну між старими станами ( і ) повинно зберегтися в якихось неконтрольованих фізичних ступенях свободи . Це можна інтерпретувати як зростання безладу (ентропії), яке в кінцевому рахунку проявиться в навколишньому середовищі у вигляді тепла. Величина енергії, необхідної для стирання одного біта, дуже мала ( ), але кінцева. Втрата енергії через незворотного стирання інформації при форматуванні жорсткого диска ємністю 1 Гб дорівнює Дж, що приблизно відповідає затратам енергії на зрушення головки диска на половину діаметра атома водню. Це на багато порядків менше реального переміщення голівки при форматуванні.
З ін угой боку, якщо ємність дисків буде рости настільки ж швидко, як в даний час, то до кінця XXIII століття для форматування жорсткого диска буде потрібно енергія, відповідна річним випромінюванню Сонця.
