Обычная программа для цифровых вычислительных машин часто производит операции, которые отбрасывают информацию об истории компьютера, оставляя машину в таком состоянии, когда сведения о непосредственно предшествующем ему состоянии неопределенны. Такие операции включают стирание данных или запись их поверх предыдущих и вход в части программы с обращением к нескольким различным инструкциям по переносу. Иначе говоря, типичный компьютер логически необратим – его функция перехода (частная функция, отображающая каждое глобальное состояние машины на последующее ему, если таковое состояние имеется) не обладает однозначной обратной функцией.

Ландауэр (Landauer [1]) сформулировал вопрос: является ли логическая необратимость неизбежной чертой полезных компьютеров? Отвечая на это положительно, он доказал физическую и философскую важность этого вопроса, показав, что, всякий раз, когда физический компьютер отбрасывает информацию о своем предыдущем состоянии, он должен порождать соответствующее количество энтропии. Следовательно, компьютер должен рассеивать энергию, не меньшую, чем $k T \ln 2$ (примерно $3 \times 10^{-21}$ Дж при комнатной температуре) на каждый стертый или потерянный иным образом бит информации.

Необратимый компьютер всегда можно сделать обратимым, сохраняя всю информацию, которая бы в других случаях терялась. Например, машине можно добавить дополнительную ленту (изначально пустую), на которую можно записывать каждую операцию, как только она будет произведена, делая это достаточно подробно так, что предшествующее состояние можно было однозначно определить по настоящему состоянию и последней записи на ленте. Однако, как отмечал Ландауэр, это только отодвинет проблему отбрасывания ненужной информации, поскольку лента должна быть очищена перед новым использованием. Таким образом, необходимы такие обратимые компьютеры, которые при остановке стирают все промежуточные результаты, оставляя только необходимые выходные и начальные входные данные. (Машина должна иметь возможность сохранять входные данные – в противном случае она не будет обратимой и по-прежнему будет проводить вычисления, при которых входные данные не определяются выходными однозначно.)

Мы покажем, что обратимые универсальные компьютеры (машины Тьюринга), удовлетворяющие этим требованиям, действительно существуют, и что нет необходимости в том, чтобы они были намного сложнее, чем необратимые компьютеры, с которыми они сравниваются. Для вычислений на обратимых компьютерах требуется примерно в два раза больше шагов, чем для вычислений на обычном, и может появиться необходимость в большем объеме рабочей памяти для временного хранения данных. Перед проведением формального доказательства проведем рассуждение на современном эвристическом уровне.

Мы начнем с уже упоминавшегося обратимого, но «неаккуратного» компьютера, который функционировал в течение долгого промежутка времени, но не сумел стереть ненужные результаты, сохранив историю своей деятельности. Ленту, заполненную случайными данными, можно очистить только необратимым процессом; однако лента, записавшая историю, не беспорядочна – существует неявная избыточная информация, которой обменивались лента и породившая историю машина. Ее и можно использовать для обратимой очистки ленты. Например, если к концу некоторого шага вычислений новая стадия вычислений задается функцией перехода, которая обратна к начальной функции перехода, то машина начнет выполнять все вычисления в обратном порядке, приведя в конце концов ленту истории в начальное пустое состояние [2]. Поскольку прямое вычисление было детерминированным и обратимым, обратное должно быть таким же. К сожалению, стадия обратного перехода трансформирует выходные данные в первоначальные входные, делая общее вычисление полностью бесполезным. Потеря нужных выходных данных может быть предотвращена просто дополнительным копированием их на отдельной ленте перед началом обратного процесса. При операции копирования (которую можно сделать обратимым образом, если лента, используемая для копирования, изначально пуста) запись на ленту истории прекращается. Тогда обратный процесс уничтожит только оригинал, но не копию. В конце вычислений в компьютере будут содержаться (реконструированные) оригинальные входные данные и неискаженная копия выходных: все остальные данные в памяти будут к этому времени восстановлены до их первоначального пустого состояния. Даже если никаких сведений об истории не останется, вычисление будет обратимым и детерминированным, поскольку таковой была каждая его стадия.

Может показаться, что одним из недостатков обратимых машин является потребность в большом объеме оперативной памяти, нужной для записи истории – для $
u$-шаговой первой стадии потребуется $
u$ записей истории. Ниже будет доказано, что при выполнении работы за более чем три стадии требуемая оперативная память часто может быть значительно сокращена. В последнем разделе обсуждается возможность обратимых физических компьютеров, способных рассеивать на каждом шаге меньшую, чем $k T$ энергию, на примере биохимических аппаратов генетических кодов.