Приведенное выше доказательство справедливо не только в случае трехленточной машины Тьюринга, но может быть применено к детерминированным автоматам любого рода, конечным или бесконечным, при единственном условии, что временная память достаточно велика для хранения истории. Существуют и одноленточные обратимые машины, но их частое переключение между рабочей областью ленты и областью записи истории требует большого количества шагов, примерно $
u^{2}$, для моделирования $
u$-шагового обратимого вычисления. Если $S$ – универсальная машина Тьюринга, то $R$ становится машиной для обратимого выполнения любой компьютерной программы. Для таких универсальных машин, служащих для любых целей, кажется весьма маловероятным, что удастся избежать необходимости частичного включения входных данных в выходные. Однако существует множество вычислений, при которых выходные данные определяются входными однозначно, и можно надеяться, что для таких задач удастся построить особый обратимый компьютер, который будет просто отображать входные данные в выходные, стирая все остальное. Это действительно возможно при условии, что мы имеем доступ к обычной машине Тьюринга, которая для имеющихся выходных данных вычисляет соответствующие входные. Пусть $S_{1}$ – (необратимая) машина Тьюринга, вычисляющая выходные данные по входным, и $S_{2}$ – машина, вычисляющая входные данные по выходным. Обратимое вычисление производится в семь стадий, как показано в таблице 2 , из которых первые три используют обратимую форму компьютера $S_{1}$ и, как в таблице 1 , служат для отображения входных данных во входные и выходные. Четвертая стадия меняет местами входные и выходные данные. Стадии пять и семь используют обратимую реализацию компьютера $S_{2}$; стадия пять имеет единственной целью воссоздание истории вычисления $S_{2}$ (то есть получение входных данных из выходных), которая, после того как дополнительные копии входных данных были стерты на стадии шесть, используется на стадии семь для уничтожения собственных данных и оставшихся копий входных данных; таким образом создаются только нужные выходные данные.
Теперь вернемся к более привычной ситуации, когда входные данные нужно сохранить, поскольку неизвестен способ их вычисления. Если производить вычисления обратимо, то это повлечет за собой только умеренное увеличение времени вычисления и сложности машины; основной недостаток обратимых компьютеров проявится, таким образом, в потребности в большом объеме оперативной памяти, необходимой для хранения истории выполнения вычислений произвольной длительности (т.е. таких, для которых число шагов $
u$ значительно превышает число клеток используемой памяти $s$ ). К счастью, требование к объему оперативной памяти может быть сильно уменьшено после разбиения работы на последовательность из $n$ сегментов, каждый из которых может быть произведен и восстановлен в памяти (а лента истории, следовательно, очищена и готова к повторному использованию) перед тем, как приступать к следующему. Каждый сегмент оставит на рабочей ленте
Таблица 2. Обратимый компьютер для конкретной задачи, в которой входные данные есть известная вычисляемая функция выходных.
(ленте 1) след своей работы, который можно использовать как входные данные для запуска следующего сегмента; но чтобы сохранить обратимость, следует оставить (скажем, на ленте 3) копии их собственных входных данных, которые в большинстве случаев могут быть просто остатками предыдущих запусков. В конце вычислений мы получим в дополнение к первоначальным входным и нужным выходным данным все $n-1$ промежуточные остатки (сосредоточенные, например, на ленте 3). Эти промежуточные результаты, которых не было бы в случае, если работа не была бы поделена на сегменты, можно либо воспринимать как непрерывные (но нежелательные) выходные данные в обмен на $n$-кратное сокращение ленты истории, либо они могут быть сами обратимо стерты после копирования нужных выходных данных (их можно поместить, скажем, в ранее неиспользовавшуюся часть ленты 3) и последующего обращения всего п-сегментного вычисления целиком. Это обращение возможно, поскольку каждый сегмент был сделан обратимым образом. Последовательность остатков, нужных для перезапуска, таким образом, функционирует как своего рода история более высокого уровня и стирается после применения на более высоком уровне того же метода, что используется для стирания начальных историй. В конце вычислений в машине будут содержаться только первоначальные входные и нужные выходные данные $n$-го сегмента, и каждый шаг первоначального необратимого вычисления будет проделан дважды в одну сторону и дважды в другую. Для работы, требующей $
u$ шагов и размера остатков для перезапуска вычислений $z$, требование на полную оперативный память (минимизированную выбором $n=\sqrt{
u / s}$ ) составляет $2 \sqrt{
u / s}$ клеток, половину на ленте истории и половину на ленте остатков. Можно достичь $\frac{1}{2} \sqrt{
u / s}$-кратного сокращения этого пространства за счет удвоения длительности счета (не считая времени, нужного для записи и чтения остатков для перезапуска) без каких-либо ненужных выходных данных. Используя систематическое обращение последовательно увеличивающихся вложенных сегментов, можно надеяться на достижение абсолютного минимума оперативной памяти, растущей только как $\ln
u$ для достаточно больших $
u$, со временем, растущим, возможно, как $
u^{2}$, поскольку число повторных обращений к сегментам растет при этом линейно.
Таким образом, оказывается, что любое вычисление может быть сделано логически обратимым без чрезмерного увеличения сложности машины, числа шагов, ненужных выходных данных или объема оперативной памяти.
