Можно построить модель только что описанной системы, используя двумерную решетку спинов величины $1 / 2$. Каждая составляющая системы моделируется как подрешетка спиновой системы. Кроме подрешеток для внутренней машины $\mathscr{L}$, вычислительной ленты $\mathscr{T}$ и вычислительной головки $\mathbf{h}$, в этой решетке выделяются подрешетки для записывающей головки $\mathbf{j}$ и записывающей системы $\mathscr{R}$. Все эти подрешетки изображены на рисунке 1 . Приведем детальное описание системы. Модель внутренней машины $\mathscr{L}$, способная воспроизвести $J$ шагов стандартной машины Тьюринга, требует для своей реализации область $R_{\mathscr{L}}$, занимающую по крайней мере $l_{2}\left(N_{J}\right)$ узлов решетки. Для удобства расположим $R_{\mathscr{L}}$ так, чтобы она содержала $J+1$ узел в $x$-направлении, занимая места от 0 до $J$, и $M$ узлов в $y$-направлении, занимая места от 0 до $M-1$. Здесь и в дальнейшем $M=l_{2}(m)$ — это длина двоичной цепочки, необходимой для представления символов в алфавите $S$. Заметим, что поскольку $N_{J} \leqslant m^{J+1}$, то в силу равенства (2) $M J+J \geqslant l_{2}\left(N_{J}\right)$. Каждое состояние $l$ внутренней машины $\mathscr{L}$, достижимое за $\leqslant J$ шагов, когда оно рассматривается как одно из чисел $\left\{1, \ldots, N_{J}\right\}$, может быть представлено как обращенное двоичное представление числа в виде конечной последовательности нулей и единиц. Например, $2=01,3=11$, $4=001$ и т. д. Здесь числа записываются в обратном порядке для того, чтобы можно было воспользоваться представлением последовательностями из нулей и единиц длины чисел $\{1, \ldots, M \cdot(J+1)\}$, добавляя справа нули без изменения значения. Поэтому в дальнейшем $l$ будет означать или число, или его расширенное двоичное представление.

Пусть $\Theta$ — некоторое отображение, которое упорядочивает узлы решетки $R_{\mathscr{L}}$. Например, $\Theta(j, k)=j M+k$ для $x$-координат $j=0, \ldots, J$ и $y$-координат $k=0, \ldots, M-1$. Отображение $\Theta$ — это биекция из $R_{\mathscr{L}}$ в $\{0,1, \ldots,[(J+1) \cdot M]-1\}$. Используя эту функцию, каждое состояние $l$ внутренней машины $\mathscr{L}$, соответствующее спиновой конфигурации $F_{l}$ в $R_{\mathscr{L}}$, можно задать формулой $F_{l}(i, j)=l(\Theta(i, j))$ для каждого узла $(i, j)$ в $R_{\mathscr{L}}$. Этот пример соответствует такому расположению представления состояния $l$ с помощью обращенного двоичного представления: сначала идут первые $M$ нулей и единиц вдоль $y$-направления при $x=0$, затем $M$ нулей и единиц с $x=1, \ldots$, и, наконец, $M$ нулей и единиц вдоль линии $x=J$.

Вычислительная лента $\mathscr{T}$ моделируется прямоугольной областью $R_{\mathscr{T}}$ длины $2 J+1$ от $-J$ до $J$ в $x$-направлении (см. рис. 1). Для каждого $j,-J \leqslant j \leqslant J$, подрешетка $R_{\mathscr{T}}$, состоящая из узлов с $x=j$ и значений $y$, изменяющихся от $M$ до $2 M-1$, соответствует $j$-й клетке на ленте. Длина ленты определяется из тех соображений, что при стандартном вычислении головка начинает свое движение с центра и за $J$ шагов не может продвинуться более чем на $J$ шагов влево или вправо.

Распространим принятое представление символов $S$ на множество $(+,-)$-последовательностей длины $M$. В этом случае описанная выше спиновая конфигурация подрешетки $R_{\mathscr{T}}$ соответствует содержимому $j$-й клетки $\mathscr{T}$. Эту конструкцию можно очевидным образом обобщить так, чтобы каждому выражению на ленте соответствовала конфигурация на решетке $R_{\mathscr{T}}$. В дальнейшем, в зависимости от контекста, $\gamma$ будет обозначать или выражение на ленте, или соответствующую спиновую конфигурацию в $R_{\mathscr{T}}$. Очевидно, что пустой клетке соответствует (-)-последовательность или спиновая конфигурация, в которой все спины подрешетки $R_{\mathscr{T}}$ направлены вниз.
Рис. 1. Представление решетчатой модели вычислительной машины. Компоненты $X$ и $Y$ положений узлов задаются числами от $-J$ до $J$ и от 0 до $2 M+L_{J}^{R}+1$ соответственно. Области решетки для компонент $\mathscr{L}, \mathbf{j}$ и $\mathscr{R}$ по оси $x$ простираются от 0 до $J$, для компонент $\mathscr{T}$ и $\mathbf{h}-$ от $-J$ до $J$. Размер и положение областей $\mathscr{L}, \mathscr{T}$ и $\mathscr{R}$ по оси $y$ показаны фигурными скобками. Узлы для головок $\mathbf{h}$ и $\mathbf{j}$ занимают ряды с координатами $Y 2 M$ и $2 M+1$ соответственно. Символ + означает спин, направленный вверх, символ — означает спин, направленный вниз, точки указывают на узлы со спином $1 / 2$

Вычислительная головка $\mathbf{h}$ моделируется как линия с фиксированной координатой $y=2 M$ и координатой $x$, изменяющейся от $-J$ до $J$. Все спины на этой линии, кроме одного, направлены вниз. Вверх направлен тот спин, положение которого соответствует положению
клетки, около которой расположена головка. Например, конфигурация $(-,-, \ldots,-,+,-, \ldots,-)$, где направленный вверх спин имеет координату $j$, представляет головку $\mathbf{h}$, расположенную около клетки $j$.

Записывающая головка $\mathbf{j}$ моделируется так же, как и $\mathbf{h}$, только теперь $y$ принимает значение $2 M+1$, а координата $x$ изменяется от 0 до $J$.

Модель записывающей системы $\mathscr{R}$ оказывается более сложной, потому что здесь с каждой клеткой, если она непустая, связывают три числа. В каждой клетке нужно записать состояние внутренней машины $\mathscr{L}$, символ, прочитанный головкой $\mathbf{h}$ и положение $\mathbf{h}$. Для первых $J$ шагов любого вычисления любой стандартной машины Тьюринга состояния внутренней машины $\mathscr{L}$ лежат в интервале $N_{J}$, содержимое клетки, сканируемой $\mathbf{h}$, лежит в $S$, положение $\mathbf{h}$ хранится в интервале $[-J, J]$.

Предположим, что существует взаимно однозначное отображение множества $\left(N_{J} \times S \times[-J, J]\right) \cup\{b\}$ на множество всех двоичных последовательностей длины $L_{J}^{\mathscr{R}}$. Дополнительный символ $b$ позволяет учесть то обстоятельство, что сканируемая клетка может быть пустой. Поскольку отображение должно быть «отображением на» или «отображением в», то должно выполняться соотношение $L_{J}^{\mathscr{R}} \geqslant l_{2}\left[\left(N_{J} \cdot m \cdot(2 J+1)+1\right]\right.$, в котором возможен и знак равенства, а $m$ — это число элементов в $S$. Стандартный пример такого отображения дает функция $\Phi$, определяемая равенством
\[
\Phi(l s j)=2_{J}(K(K(l, s), u(j))+1),
\]

а $\Phi(b)=2_{J}(0)$. В этом равенстве функция $u$ отображает отрезок $[-J, J]$ на $[0,2 J]$ по правилу $u(j)=2 j+1$, если $j>0$ и $u(j)=-2 j$, если $j \leqslant 0$. $K$ — функция двух переменных [17], определенная формулой
\[
K(m, n)=\frac{1}{2}\left(m^{2}+2 m n+n^{2}+3 m+n\right) .
\]

Символ $s$ в правой части (5) означает, что $s$ — одно из чисел из $[1, \ldots, m]$. Символ $2_{J}(n)$ определяет обычное двоичное представление числа $n$, дополненное слева нулями, так, чтобы длина числа $2_{J}(n)$ была равна $L_{J}^{\mathscr{R}}$ для всех $n \leqslant\left[N_{J} \cdot m \cdot(2 J+1)\right]+1$.
Область $R_{\mathscr{R}}$ решетки $\mathscr{R}$ расположена от 0 до $J$ в $x$-направлении и от $2 M+2$ до $2 M+1+L_{J}^{R}$ в $y$-направлении (рис. 1). Содержимое $k$-й записывающей клетки моделируется спинами в подрешетке $R_{\mathscr{R}}$ с координатами $x=k$ и $2 M+2 \leqslant y \leqslant 2 M+1+L_{J}^{R}$. Представление $2_{J}(j)$ числа $j$ построено так, что для координаты $y=2 M+2+n(+)$-спин соответствует числу $1 \times 2^{n}$, а (-)-спин — $0 \times 2^{n}$. Этим определяется двоичное представление
\[
j=\sum_{n=0}^{L_{J}^{R}}\left[2_{J}(j)\right](n) \cdot 2^{n} .
\]

Пусть $\phi$ будет отображением $[0, J]$ в $\left(N_{J} \times S \times[-J, J]\right) \cup\{b\}$. Тогда $\phi$ определяет регистрирующую систему, так что $\phi(k)$ — это содержимое $k$-й регистрирующей клетки. Отображением $\phi$ можно воспользоваться для построения спиновой конфигурации $G_{\phi}$ на решетке $R_{\mathscr{R}}$, в каждой точке $(k, 2 M+2+j)$ которой
\[
G_{\phi}(k, 2 M+2+j)=[\Phi(\phi(k))](j) .
\]

Для простоты и для того, чтобы иметь возможность представления любых машин одной фиксированной решеткой, ее размер выбран большим, чем это необходимо. Например, если думать о реализации только одной машины, то можно значительно уменьшить размеры $R_{\mathscr{R}}$ и $R_{\mathscr{L}}$.

Полезно привести пример явной реализации только что построенного представления. Пусть $S=\left(b, s_{1}, s_{2}\right)$, где $\left(b, s_{1}, s_{2}\right)$ соответствуют числам $0,1,2$. В этом случае $m=3$ и $l_{2}(m)=2$. Пусть $J=5$. Рисунок 2 изображает состояние решетки после двукратного применения тройки операций «запись-вычисление- $\mathbf{j}$-сдвиг», которые управляются пятерками $1(b, 1,-1) 3$ и $3(b, 2,0) 5$. Конфигурация в $R_{\mathscr{L}}$, соответствующая обращенному двоичному представлению числа 5 , или $1010 \ldots 0$, представляет внутреннюю машину $\mathscr{L}$ в состоянии 5 . Выражение на ленте $\mathscr{T}$, прочитанное слева направо, гласит $b b b s_{2} s_{1} s_{2} s_{1} s_{1} s_{2} s_{1}$. В частности, символ $s_{2}$, находящийся при $x=-1$, а $s_{1}$ — при $x=0$ с последующими символами ( $s_{2} s_{1} s_{1} s_{2} s_{1}$, которые произвольны), задаются как часть стандартного входа. Головка $\mathbf{h}$, как определено пя-
Рис. 2. Решеточная модель спиновой конфигурации для примера в тексте. Двунаправленные стрелки означают узлы со спином, направленным вниз. Как и на предыдущем рисунке, области, связанные с определенными составляющими системы, обозначены фигурными скобками и/или рукописными буквами

терками, находится в положении -1 , а головка $\mathbf{j}$ — в положении 2 , сканируя пустую клетку записи. Все клетки справа от $\mathbf{j}$ также пусты. Протяженность подрешетки $\mathscr{R}$ в $y$-направлении дается выражением $L_{J}^{R}=l_{2}\left(N_{J} \cdot m \cdot(2 J+1)+1\right)$. Поскольку $N_{J}=364$ (см. равенство (2)), то $L_{J}^{R}=14$. Пятерки означают, что в первой и второй клетках записи находится следующее: $(1,0,0)$ и $(3,0,-1)$. Значения функции $\Phi$ : $\Phi(1,0,0)=2_{J}(6)=\ldots 110$ и $\Phi(3,0,-1)=2_{J}(76)=\ldots 1001100$ записаны в клетках 0 и 1 подрешетки $\mathscr{R}$. Это показано на рисунке 2 .