Поскольку машины Тьюринга подробно описаны в литературе $[2$, 16], мы ограничимся кратким изложением проблемы. Машина Тьюринга состоит из трех частей: внутренней машины $\mathscr{L}$, вычислительной ленты $\mathscr{T}$ и вычислительной головки h. Состояния $\mathscr{L}$ можно представить числами $0,1, \ldots$ из $\mathbb{N}, \mathscr{T}$ – это лента, состоящая из бесконечного числа клеток, каждая из которых может находиться в одном из конечного числа состояний из $S$ – алфавита символов. Особый элемент из $S-b$ – обозначает пустую клетку. На ленте $\mathscr{T}$ можно написать выражения – последовательности символов $\gamma: \mathbb{Z} \rightarrow S$, где $\mathbb{Z}$ – множество целых чисел и $\gamma(j)=b$, исключая не более чем конечное число значений $j$.

Элементарные операции машины задаются пятерками $l\left(s, s^{\prime}, \alpha\right) l^{\prime}$, каждая из которых означает, что $\mathscr{L}$ в состоянии $l$ и символ $s$ в клетке из $\mathscr{T}$, только что прочитанный $\mathbf{h}$, переходят в состояния $l^{\prime}$ и $s^{\prime}$, а головка $\mathbf{h}$ перемещается на одну клетку вправо $(\alpha=+1)$ или влево $(\alpha=-1)$, либо остается на месте $(\alpha=0)$. Каждая машина Тьюринга соответствует конечному множеству пятерок $Q$, в котором нет пятерок, начинающихся с двух одинаковых символов. Если в конце некоторого шага $\mathscr{L}$ находится в состоянии $l$, а $s$ – символ, прочитанный $\mathbf{h}$, то следующий шаг задается пятеркой вида $l(s,-,-)-$. Если такой пятерки в $Q$ нет, то машина останавливается.

Каждая машина $Q$ определяет функцию $\tau_{Q}: \mathbb{N} \times S \rightarrow \mathbb{N} \times S \times$ $\times\{-1,0,1\}$, где
\[
\tau_{Q}(l s)=\left(l^{\prime} s^{\prime} \alpha\right)
\]

для каждой пары $(l s)$ из пятерки $l\left(s s^{\prime} \alpha\right) l^{\prime}$, принадлежащей $Q$. Если в $Q$ нет пятерки, начинающейся с $l$ и $s$, то $\tau_{Q}(l S)=(l s 0)$.

С помощью функции $\tau_{Q}$ можно определить функцию перехода машины $T_{Q}$ как отображение $T_{Q}: I D \rightarrow I D$, где $I D=\mathbb{N} \times(S)_{b}^{\mathbb{Z}} \times \mathbb{Z}-$ множество мгновенных описаний машины. Приведем явное выражение функции $T_{Q}$ :
\[
T_{Q}(l \gamma(j))=\left(l^{\prime} \gamma^{\prime} j^{\prime}\right),
\]
где $\tau_{Q}(l, \gamma(j))=\left(l^{\prime}, \gamma^{\prime}(j), \alpha\right), j^{\prime}=j+\alpha$ и $\gamma^{\prime}(k)=\gamma(k)$ для всех $k
eq j$. Шаги $Q$ соответствуют итерациям $T_{Q}$, и процесс вычисления останавливается в неподвижной точке $Q$.

Удобно ограничиться такими машинами Тьюринга, которые выполняют вычисления в стандартной форме. В этом случае начальное состояние определяется как состояние «1», головка $\mathbf{h}$ читает символ в клетке «0» из $\mathscr{T}$ и каждое выражение $\gamma_{i}(j)=b$, если $j<0$, и не существует двух непустых состояний символов в $\gamma_{i}$, разделенных пустым. В этом случае после $n$ шагов вычислений стандартной машины Тьюринга состояние внутренней машины $\mathscr{L}$ находится среди первых $N_{n}$ чисел из $\mathbb{N}$, где
\[
N_{n}=\sum_{j=0}^{n} m^{j} .
\]

Здесь и далее $m$ – число символов в алфавите $S$. Стандартное конечное состояние похоже на начальное, следует только принять во внимание, что теперь это – одно из допустимых состояний.

Нам понадобятся числа, которые представляют в решетчатой модели двоичные цепочки спинов, направленных вверх (+) и вниз (-).

Для представления всех положительных чисел, не превосходящих $n$, требуется $l_{2}(n)$ двоичных цепочек, где
\[
l_{2}(n)=\left\{\begin{array}{lll}
{\left[\log _{2}(n)\right]+1,} & \text { если } \log _{2}(m)-\left[\log _{2}(m)\right]>0, \\
\log _{2}(n), & \text { если } \log _{2}(m)-\left[\log _{2}(m)\right]=0,
\end{array}\right.
\]

где $[r]$ означает наибольшее целое число, содержащееся в $r$. Пустые клетки $\mathscr{T}$ моделируются цепочками (-)-спинов. В представлении двоичных чисел на решетке спинов (+)-спины соответствуют единице, а (-)-спины – нулю. Таким образом, каждая пустая клетка $\mathscr{T}$ соответствует числу 0 , записанному в клетке.

В дальнейшем будут рассматриваться системы, которые моделируют только $J$ первых шагов стандартной машины Тьюринга. Это ограничение, вызываемое исключительно интересами математической простоты, позволяет избежать бесконечномерных квантовых систем. Теперь состояния внутренней машины $\mathscr{L}$ будут находиться среди чисел $\left\{1,2, \ldots, N_{j}\right\}$.
Вообще говоря, функция перехода $T_{Q}$ машины Тьюринга не взаимно однозначна. Чтобы построить гамильтонову модель дискретного процесса, необходимо иметь взаимно однозначную функцию перехода. Это можно сделать, добавив записывающую систему $\mathscr{R}$ и записывающую головку j. В этом случае каждый шаг машины Тьюринга будет связан с операциями трех типов: запись, вычисление, сдвиг. При операции записи состояние внутренней машины $\mathscr{L}$, запись в клетке из $\mathscr{T}$, прочитанная головкой $\mathbf{h}$, и положение $\mathbf{h}$ записываются в пустой клетке из $\mathscr{R}$. Эти клетки сканирует головка j. При операции вычисления состояния внутренней машины $\mathscr{L}$ запись в клетке из $\mathscr{T}$ и положение головки $\mathbf{h}$ изменяются так, как это предписывает пятерка из $Q$, два первых символа которой записаны в клетке из $\mathscr{R}$, осмотренной головкой $\mathbf{j}$. Третий тип операции – сдвиг $\mathbf{j}$ к новой клетке записи. Эти три типа операций моделируются на спиновой решетке или как три типа преобразований, повторяющихся снова и снова (раздел 4), или как повторные преобразования одного типа (раздел 5).