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

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

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

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

С помощью функции ${\tau }_Q$ можно определить функцию перехода машины $T_Q$ как отображение $T_Q:ID\to ID$, где $ID=\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))=(l^{\prime },{\gamma }^{\prime }(j),\alpha ),j^{\prime }=j+\alpha$ и ${\gamma }^{\prime }(k)=\gamma (k)$ для всех $keqj$. Шаги $Q$ соответствуют итерациям $T_Q$, и процесс вычисления останавливается в неподвижной точке $Q$.

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

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

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

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

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

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