Категория $\mathscr{C}$, определенная выше, называется конструктивной вселенной, если она содержит конструктивный мир $\mathbf{N}$ всех целых чисел $\geqslant 1$, конечных множеств $\varnothing,\{1\}, \ldots,\{1, \ldots, n\}, \ldots$ и удовлетворяет следующим условиям (a)-(d).
(a) $\mathscr{C}(\mathbf{N}, \mathbf{N})$ определено как множество всех частично-рекурсивных функций (см., например, [Ma1], Гл. V, или [Sa]).
(b) Любой бесконечный объект $C$ изоморфен $\mathbf{N}$.
(c) Если $U$ бесконечно, то $\mathscr{C}(U, V)$ состоит из всех частичных отображений $U \rightarrow V$. Если $V$ конечно, то $\mathscr{C}(U, V)$ состоит из таких $f$, что прообраз любого элемента $V$ перечислим.

Перед формулированием последнего условия (d) сделаем некоторые комментарии.

Предложение (b) — часть известного тезиса Чёрча. Любой изоморфизм (вычислимая биекция) $\mathbf{N} \rightarrow U$ в $\mathscr{C}$ называется нумерацией. Таким образом, две разные нумерации одного и того же конструктивного мира отличаются рекурсивной перестановкой N. Мы будем называть такие нумерации эквивалентными. Заметим, что из-за (с) два конечных конструктивных мира изоморфны, если и только если они имеют одну и ту же мощность, и группа автоморфизмов любого конечного $U$ состоит из всех перестановок $U$.

Принципиально мы всегда рассматриваем $\mathscr{C}$ как открытую категорию, и в любой момент разрешаем себе добавить к ней новые конструктивные миры. Если некоторый бесконечный $U$ добавляется к $\mathscr{C}$, он должен войти в нее с некоторым классом эквивалентных нумераций. Так, любое конечное объединение конструктивных миров может быть естественным образом превращено в конструктивный мир так, что погружения становятся вычислимыми морфизмами, а их образы — разрешимыми. Другой пример — мир $\mathbf{N}^{*}$ конечных последовательностей чисел из $\mathbf{N}$ («слова в алфавите $\mathbf{N}$ ») снабжен геделевой нумерацией
\[
\left(n_{1}, n_{2}, \ldots, n_{k}, \ldots\right) \rightarrow 2^{q} 3^{n_{1}-1} \ldots p_{k+1}^{n_{k}-1}-1,
\]

где $p_{k}-k$-е простое число, $q=\max \left\{i \mid n_{k}=\ldots=n_{k-i+1}=1\right\}$. Следовательно, мы можем предположить, что $\mathscr{C}$ замкнута по отношению к конструкции $U \mapsto U^{*}$. Все естественные функции, такие как длина слова $U^{*} \rightarrow \mathbf{N}$ или $i$-я буква слова $U^{*} \rightarrow U$, вычислимы.
Подобным же образом $\mathscr{C}$ может быть сделана замкнутой по отношению к конечным прямым произведениям с помощью использования (обратной) нумерации для $\mathbf{N}^{2}$ :
\[
(m, n) \mapsto m+\frac{1}{2}(m+n-1)(m+n-2) .
\]

Проекции, диагональные отображения, отображения $V \rightarrow U \times V, v \mapsto$ $\mapsto\left(u_{0}, v\right)$ все вычислимы.

Разрешимые подмножества конструктивных миров также конструктивны.

Вместо явной конструкции нумерации часто используется тезис Чёрча, который утверждает, что категория $\mathscr{C}$ определена однозначно $c$ точностью до эквивалентности.

Сейчас мы перейдем к свойствам вычислимости множеств морфизмов $\mathscr{C}(U, V)$. Теперь опять принципиально, что $\mathscr{C}(U, V)$ само не конструктивный мир, если $U$ бесконечно. Чтобы описать ситуацию аксиоматически, рассмотрим, во-первых, любую диаграмму
\[
\text { ev : } P \times U \rightarrow V
\]

в $\mathscr{C}$. Она определяет частичное отображение $P \rightarrow \mathscr{C}(U, V), p \mapsto \bar{p}$, где $\bar{p}(u):=\mathrm{ev}(p, u)$. Мы будем говорить, что конструктивный мир $P=P(U, V)$ вместе с оценивающим отображением еу есть метод программирования (для вычисления некоторых отображений $U \rightarrow V$ ). Он называется универсальным, если выполнены следующие два условия. Во-первых, отображение $P \rightarrow \mathscr{C}(U, V)$ должно быть сюръективным. Во-вторых, для любого метода программирования $Q=Q(U, V)$ с теми же самыми источником $U$ и целью $V, \mathscr{C}(Q, P)$ содержит морфизмы трансляции
\[
\text { trans : } Q(U, V) \rightarrow P(U, V),
\]

которые, по определению, всюду определенные вычислимые отображения $Q \rightarrow P$ такие, что если $q \mapsto p$, то $\bar{q}=\bar{p}$.

Теперь мы завершим определение 1.2 , добавив последнюю аксиому, формирующую часть тезиса Чёрча.
(d) Для любых двух конструктивных миров $U, V$ существуют универсальные методы программирования.
Стандартные примеры $P$ для $U=V=\mathbf{N}$ — машины Тьюринга или рекурсивные функции (точнее говоря, формализованные описания тех и других).

Из (d) следует, что композиция морфизмов может быть поднята до вычислимых функций на уровне методов программирования. Точнее говоря, если $Q$ (соответственно, $P$ ) — метод программирования для $U, V$ (соответственно $V, W$ ), и $R$ — универсальный метод программирования для $U, W$, то существуют вычислимые отображения композиции
\[
\text { comp : } P(V, W) \times Q(U, V) \rightarrow R(U, W),(p, q) \mapsto r
\]

такие, что $\bar{r}=\bar{p} \circ \bar{q}$.
Конкретный вид $P(U, V)$ уточняется выбором того, что называется в компьютерных науках «моделью вычислений». Это последнее понятие включает подробное описание не только программ, но также и всех шагов вычислительного процесса. На этом этапе впервые появляются модели кинематики и динамики процесса, и можно начать обсуждение квантования.

Формализованное описание первых $n$ шагов будет называться историей вычисления или для краткости протоколом (длины $n$ ). Для фиксированной модели протоколы (любых длин) также образуют конструктивный мир. Мы дадим две формализованные версии этого понятия для функций с бесконечными и конечными областями определения соответственно. Первая будет хорошо подходить для обсуждения вычислимости за полиномиальное время, вторая — основа для квантового вычисления.