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

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

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

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

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

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

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

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

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

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

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

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

Полезно привести пример явной реализации только что построенного представления. Пусть $S=(b,s_1,s_2)$, где $(b,s_1,s_2)$ соответствуют числам $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_{\mathcal{L}}$, соответствующая обращенному двоичному представлению числа 5 , или $1010\dots 0$, представляет внутреннюю машину $\mathcal{L}$ в состоянии 5 . Выражение на ленте $\mathcal{T}$, прочитанное слева направо, гласит $bbb{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}$ также пусты. Протяженность подрешетки $\mathcal{R}$ в $y$-направлении дается выражением $L_J^R=l_2(N_J\cdot m\cdot (2J+1)+1)$. Поскольку $N_J=364$ (см. равенство (2)), то $L_J^R=14$. Пятерки означают, что в первой и второй клетках записи находится следующее: $(1,0,0)$ и $(3,0,-1)$. Значения функции $\mathrm{\Phi }$ : $\mathrm{\Phi }(1,0,0)=2_J(6)=\dots 110$ и $\mathrm{\Phi }(3,0,-1)=2_J(76)=\dots 1001100$ записаны в клетках 0 и 1 подрешетки $\mathcal{R}$. Это показано на рисунке 2 .