Пусть $U$ – бесконечный конструктивный мир. В этой секции мы будем рассматривать частичные функции $U \rightarrow U$. Более общий случай $U \rightarrow V$ может быть сведен к этому переходом к $U \amalg V$.

Нормальная модель вычислений – это структура $(P, U, I, F, s)$, состоящая из четырех множеств и отображения:
\[
I \subset U, F \subset P \times U, s: P \times U \rightarrow P \times U .
\]
Здесь $s$ – такая всюду определенная функция, что $s(p, u)=\left(p, s_{p}(u)\right)$ для любой $(p, u) \in P \times U$. С содержательной точки зрения $p$ – программа подсчета времени, а $s_{p}(u)$ – новая конфигурация, полученная из $u$ после одного временного такта. Два добавочных подмножества $I \subset U$ (начальные конфигурации или входы) и $F \subset P \times U$ (заключительные конфигурации) должны быть заданы так, что если $(p, u) \in F$, то $s(p, u)=(p, u)$, т. е. $u$ – неподвижная точка $s_{p}$.

Далее, через $f_{p}$ мы обозначаем такую частичную функцию $f_{p}$ : $I \rightarrow U$, что
\[
\begin{array}{c}
u \in D\left(f_{p}\right) \text { и } f_{p}(u)=v \Longleftrightarrow \\
\Longleftrightarrow \text { для некоторых } n \geqslant 0,\left(p, s_{p}^{n}(u)\right) \in F \text { и } s_{p}^{n}(u)=v .
\end{array}
\]

Минимальное из таких $n$ будет называться временем (числом временных тактов), необходимых для вычисления $f_{p}(u)$ с использованием программы $p$.
Любая конечная последовательность
\[
\left(p, u, s_{p}(u), \ldots, s_{p}^{m}(u)\right), u \in I,
\]

будет называться протоколом вычисления длины $m$.
Теперь добавим условия конструктивности.
Мы потребуем, чтобы $P, U$ были конструктивными мирами, $s$ вычислимым. Кроме того, мы будем предполагать, что $I, F$ – разрешимые подмножества $U$ и $P \times U$ соответственно. Тогда $f_{p}$ – вычислимы и протоколы данной длины (произвольной длины или, соответственно, останавливающиеся в $F$ ) образуют конструктивные миры. Если мы обозначим через $Q$ мир протоколов, останавливающихся в $F$, а через еv : $Q \times U \rightarrow U$ – отображение $(p, u) \mapsto s_{p}^{\max }(u)$, то мы получим метод программирования.

Такая модель называется универсальной, если соответствующий метод программирования универсален.

Понятие нормальной модели вычислений обобщает как нормальные алгоритмы, так и машины Тьюринга. Подробно об этих понятиях см., например, [Sa], Гл. 4. В широком смысле, $p \in P$ – список подстановок алгоритма Маркова или таблица, определяющая работу машины Тьюринга. Тогда миры $U, I, F$ состонт из разных слов в рабочем алфавите.