В этом разделе формализуется доказательство предыдущего раздела. Показывается, что если имеется обычная машина Тьюринга $S$, то можно построить обратимую трехленточную машину Тьюринга $R$, которая ничем не хуже $S$ при любых стандартных входных данных и в конце вычислений даже превосходит ее, оставляя только эти входные данные и требуемые выходные. Машина $R$, как описано выше, производит вычисления в три стадии, третья стадия посвящена описанию работы первой стадии. Если читателя не интересуют подробности доказательства, он может опустить оставшуюся часть этого раздела.

Обычная одноленточная машина Тьюринга [3] состоит из контрольного модуля, головки чтения-записи и бесконечной ленты, разделенной на клетки. Ее поведение определяется конечным набором формул перехода (обычно называемых пятерками) типа ввод-вывод-сдвиг. Пятерки выглядят так:
\[
A T \rightarrow T^{\prime} \sigma A^{\prime},
\]

это означает, что если контрольный модуль находится в состоянии $A$ и головка сканирует на ленте символ $T$, то головка сначала запишет $T^{\prime}$ на месте $T$, затем сдвинется на одну клетку влево, на одну клетку вправо или останется на месте в соответствии со значением $\sigma(-,+$, или 0 соответственно); наконец контрольный модуль перейдет в состояние $A^{\prime}$. В обычном обобщении на $n$-ленточные машины все $-T, T^{\prime}$ и $\sigma$ в пятерке представляют собой совокупности $n$ индексов $-n$-плеты.

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

Чтобы сделать машину Тьюринга обратимой, мы должны добавить переходы, которые напоминают инверсии уже имеющихся переходов. Однако, поскольку операции записи и сдвига не коммутируют, инверсия пятерки ввод-вывод-сдвиг хотя и существует, но имеет другой вид, а именно: сдвиг-ввод-вывод. При конструировании обратимой машины необходимо иметь пятерки обоих типов или использовать формализм, в котором переходы и их инверсии имеют одну и ту же форму. Здесь будет использована вторая возможность – в обратимой машине использован простой тип формулы перехода, в которой во время данного перехода каждая лента подвергается операции ввода-вывода или операции сдвига, но ни одна лента не подвергается обеим операциям одновременно.

Определение. Квадруплетом (для $n$-ленточной машины Тьюринга, имеющей по одной головке на ленту) называется выражение вида
\[
A\left[t_{1}, t_{2}, \ldots, t_{n}\right] \rightarrow\left[t_{1}^{\prime}, t_{2}^{\prime}, \ldots, t_{n}^{\prime}\right] A^{\prime},
\]

где $A$ и $A^{\prime}$ – положительные целые числа (обозначающие внутренние состояния контрольного модуля до и после перехода соответственно); каждое $t_{k}$ может быть или положительным целым числом, обозначающим символ, который должен быть прочитан на $k$-й ленте, или косой чертой (/), обозначающей, что при переходе считывания с $k$-й ленты не происходит; каждое $t_{k}^{\prime}$ является или положительным целым числом, обозначающим символ, который должен быть написан на $k$-й ленте, или элементом набора $(-, 0,+)$, который обозначает левый, нулевой или правый сдвиг головки на $k$-й ленте. Для каждой ленты $k, t_{k}^{\prime} \in(-, 0,+)$ тогда и только тогда, когда $t_{k}=/$. Таким образом, машина записывает на ленту в том и только в том случае, если она только что прочитала что-то, и сдвигает ленту в том и только в том случае, если она ничего не читала перед этим.
Как и пятерки, квадруплеты определяют взаимно однозначные отображения глобальных состояний машины. Любую пятерку «ввод-вывод – сдвиг» можно разделить на «ввод – вывод» и «сдвиг», которые можно представить как квадруплеты. Например, пятерка (1) эквивалентна паре квадруплетов
\[
\begin{array}{c}
A T \rightarrow T^{\prime} A^{\prime \prime}, \\
A^{\prime \prime}[/ / \cdots /] \rightarrow \sigma A^{\prime},
\end{array}
\]

где $A^{\prime \prime}$ – новое состояние контрольного модуля, отличное от $A$ и $A^{\prime}$. Когда различные пятерки разбиты таким образом, для каждого надо использовать различные связанные состояния $A^{\prime \prime}$, чтобы избежать трудностей, связанных с неопределенностью ввода.

Квадруплеты имеют важные свойства, справедливость которых можно проверить непосредственно. Пусть
\[
\alpha \equiv A\left[t_{1}, \ldots, t_{n}\right] \rightarrow\left[t_{1}^{\prime}, \ldots, t_{n}^{\prime}\right] A^{\prime}
\]

и
\[
\beta \equiv B\left[u_{1} \ldots, u_{n}\right] \rightarrow\left[u_{1}^{\prime}, \ldots, u_{n}^{\prime}\right] B^{\prime}
\]
– два $n$-ленточных квадруплета.
1) $\alpha$ и $\beta$ взаимно обратны (определяя обратные отображения глобальных состояний машины) в том и только том случае, если $A=B^{\prime}$ и $B=A^{\prime}$, и для каждого $k$ либо ( $t_{k}=u_{k}=/$ и $\left.t_{k}^{\prime}=-u_{k}^{\prime}\right)$, либо $\left(t_{k}
eq /\right.$ и $t_{k}^{\prime}=u_{k}$ и $t_{k}=u_{k}^{\prime}$ ). Другими словами, обращение квадруплета достигается в том случае, если меняются местами начальное и конечное состояния контрольного модуля, символы ввода и символы вывода и знаки всех сдвигов.
2) Области определений $\alpha$ и $\beta$ перекрываются тогда и только тогда, когда $A=B$, и для каждого $k\left(t_{k}=/\right.$ или $u_{k}=/$ или $\left.t_{k}=u_{k}\right)$. Непересечение областей определения требует различных начальных состояний контрольного модуля или различных сканируемых символов на какой-нибудь ленте, читаемой обоими квадруплетами.
3) Области значений $\alpha$ и $\beta$ перекрываются тогда и только тогда, когда $A^{\prime}=B^{\prime}$, и для каждого $k\left(t_{k}=/\right.$ или $u_{k}=/$ или $\left.t_{k}^{\prime}=u_{k}^{\prime}\right)$. Это свойство аналогично предыдущему, но зависит от конечного состояния контрольного модуля и записанных на ленту символов.
Обратимая, детерминированная -ленточная машина Тьюринга может быть определена как конечный набор $n$-ленточных квадруплетов, области определений и значений которых не пересекаются для любой пары лент. Теперь мы хотим показать, что такие машины можно построить по образцу обычных (необратимых) машин Тьюринга. Удобно потребовать, чтобы при этом выполнялись определенные требования стандартизации формата, что, однако, не ограничивает существенно вычислительные возможности машин.

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

Определение. Стандартной машиной Тьюринга называется набор одноленточных пятерок
\[
A T \rightarrow T^{\prime} \sigma A^{\prime},
\]

удовлетворяющих следующим условиям.
1) Детерминизм. Не существует двух пятерок, отвечающих одним и тем же $A$ и $T$ одновременно.
2) Формат. Начав с контрольного состояния $A_{1}$ при любых стандартных исходных данных, машина, если она остановится, окажется в контрольном состоянии $A_{f}$ (где $f$ – номер контрольного состояния), не выйдя из стандартного формата.
3) Особые пятерки. В машине содержатся следующие пятерки
\[
\begin{array}{c}
A_{1} b \rightarrow b+A_{2}, \\
A_{f-1} b \rightarrow b 0 A_{f},
\end{array}
\]

и контрольные состояния $A_{1}$ и $A_{f}$ больше ни в каких других пятерках не встречаются. Таким образом, эти два состояния выполняются первым и последним, соответственно, в любом законченном вычислении при стандартных выходных данных. Буква $b$ обозначает пробел.
Фраза «машина $M$ при вводе стандартного набора входных данных $I$ вычисляет набор стандартных выходных данных $P$ » будет заменятся сокращением $M: I \rightarrow P$. Для $n$-ленточной машины это выглядит как $M:\left(I_{1} ; I_{2} ; \ldots ; I_{n}\right) \rightarrow\left(P_{1} ; P_{2} ; \ldots ; P_{n}\right)$, где $I_{k}$ и $P_{k}$ – стандартные входные и стандартные выходные данные на $k$-й ленте. Пустая лента будет обозначена как $B$.
Теперь можно сформулировать нашу основную теорему.
Теорема. Для каждой стандартной одноленточной машины Тьюринга $S$ существует трехленточная обратимая детерминированная машина Тьюринга $R$, такая, что если $I$ и $P$ – потоки алфавита машины $S$, не содержащие пробелов, то $S$ останавливается на $I$ в том $u$ только в том случае, если $R$ останавливается на $(I ; B ; B)$, и $S: I \rightarrow P$ в том и только том случае, если $R:(I ; B ; B) \rightarrow(I ; B ; P)$.

Более того, если $S$ имеет $f$ контрольных состояний, $N$ пятерок и алфавит ее ленты состоит из $z$ букв, включая пробелы, то $R$ будет иметь $2 f+2 N+4$ состояний, $4 N+2 z+3$ квадрулета и алфавиты лент из $z, N+1$ и $Z$ букв соответственно. Наконец, если при каком-нибудь вычислении на $S$ требуется $
u$ шагов, используется $s$ клеток ленты, и это порождает выходные данные длины $\lambda$, то для $R$ потребуется $4
u+4 \lambda+5$ шагов и s, $
u+1$ и $\lambda+2$ клеток на ее трех лентах соответственно. (Ниже будет доказано, что когда $
u \gg s$, общее требуемое пространство может быть уменьшено до величины, меньшей, чем $2 \sqrt{
u z}$.)
Доказательство.
Чтобы построить машину $R$, нужно начать с упорядочения $N$ пятерок машины $S$ так, чтобы первая и последняя пятерки были
\[
\begin{array}{l}
\text { 1) } A_{1} b \rightarrow b+A_{2}, \\
\vdots \\
m) A_{j} T \rightarrow T^{\prime} \sigma A_{k}, \\
\vdots \\
\text { N) } A_{f-1} b \rightarrow b 0 A_{f} .
\end{array}
\]

выше. В этом случае $m$-я пятерка превратится в
\[
\left\{\begin{array}{l}
A_{j} T \rightarrow T^{\prime} A_{m}^{\prime}, \\
A_{m}^{\prime} / \rightarrow \sigma A_{k} .
\end{array}\right.
\]

Дополнительные состояния $A_{m}^{\prime}$ отличаются от старых состояний и друг от друга: каждое $A^{\prime}$ появляется только в одной паре квадруплетов.

Затем добавляются две дополнительные ленты: одна для записи истории, другая для дублирования выходных данных. Лента вывода (третья) остается пустой и не сдвигается на настоящий момент, а лента истории (вторая) служит для записи индекса $m$, как только выполнена пара переходов.
Тогда $m$-я пара квадруплетов принимает вид:
\[
\left\{\begin{array}{l}
A_{j}[T / b] \rightarrow\left[T^{\prime}+b\right] A_{m}^{\prime}, \\
A_{m}^{\prime}[/ b /] \rightarrow[\sigma m 0] A_{k} .
\end{array}\right.
\]

Заметим, что лента записи истории (вторая) не совпадает по фазе с двумя другими – запись на нее идет, когда те сдвигаются, и наоборот. Такая корреляция фаз необходима, чтобы обеспечить обратимость она служит для сбора информации, которая в противном случае была бы потеряна, когда специфическое контрольное состояние $A_{m}^{\prime}$ переходит в более общее состояние $A_{k}$. Положительный (+) сдвиг ленты истории обеспечивает готовность пустой клетки воспринять следующую величину $m$. Если вычисления $S$, равно как и вычисления $R$, не остановлены, машина будет продолжать печать ленты истории неограниченно. С другой стороны, если (при стандартном вводе) $S$ останавливается, то $R$ в конце концов выполнит $N$-ю пару квадруплетов, находясь в состоянии $A_{f}$, со стандартным выводом на ленту 1 . Головка истории будет сканировать номер $N$, который был только что записан в самую крайнюю правую позицию ленты истории 2 (см. таблицу 1). Контрольное состояние для этой стадии обозначено через $B^{\prime}$ и отличается от всех контрольных состояний типа $A$. Заметим, что процесс копирования можно сделать обратимым, при этом на ленте истории больше ничего писать не нужно. Это показывает, что создание (или уничтожение) дубликата данных не требует отбрасывания информации.

Таблица 1. ${ }^{1}$ Структура и действие трехленточной обратимой машины Тьюринга. Вычисления производятся в три стадии с использованием различных наборов квадруплетов и контрольных состояний, связь проявляется через состояния $A_{f}$ и $C_{f}$. Справа символически показано содержимое лент в начале и конце каждой стадии. Подчеркивание показывает положение головки. Начальное состояние – $A_{1}, C_{1}$ – конечное состояние для выполненного вычисления.
${ }^{1}$ Метки 1)…m) …N) не являются частью машины. Они отражают соответствие пятерок оригинальной необратимой машины, которую модулирует обратимая машина.

На второй стадии маленькие скобки обозначают набор квадруплетов для каждой непустой литеры ленты $x$.
Третья стадия отменяет работу первой и состоит в инверсии всех переходов первой стадии с заменой $A$ на $C$. В конечном состоянии $C_{1}$ лента истории снова пуста, и другие ленты содержат восстановленные входные и нужные выходные данные.

Как показано в таблице 1 , общее число контрольных состояний равно $2 N+2 f+4$, число квадруплетов $4 N+2 z+3$, при этом вычисление требует столько времени и столько клеток, сколько было упомянуто в начале доказательства. Неперекрываемость областей определения и значения для всех квадруплетов обеспечивает детерминизм и обратимость машины $R$. На первой стадии верхние переходы каждой пары не перекрываются в их областях определений из-за принятой за аксиому детерминированности машины Тьюринга $S$, чьи пятерки также начинаются с $A_{j} T \rightarrow$. Области значений верхних квадруплетов (как и области определений нижних) предохраняются от перекрывания единственностью состояния $A_{m}^{\prime}$. Наконец, область значений нижних квадруплетов защищена от перекрывания единственностью выходных данных $m$ на ленте истории. Состояние $A_{f}$ не доставляет хлопот, даже если оно появляется как на стадии 1 , так и на стадии 2 , потому что по определению машины $S$ оно не появляется слева на стадии 1 ; то же относится и к состоянию $C_{f}$. Неперекрываемость на стадии 2 можно проверить, в то время как детерминизм и обратимость стадии 3 следуют из этих свойств стадии 1.