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

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

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

Принципиально мы всегда рассматриваем $\mathcal{C}$ как открытую категорию, и в любой момент разрешаем себе добавить к ней новые конструктивные миры. Если некоторый бесконечный $U$ добавляется к $\mathcal{C}$, он должен войти в нее с некоторым классом эквивалентных нумераций. Так, любое конечное объединение конструктивных миров может быть естественным образом превращено в конструктивный мир так, что погружения становятся вычислимыми морфизмами, а их образы — разрешимыми. Другой пример — мир ${\mathbf{N}}^{\ast }$ конечных последовательностей чисел из $\mathbf{N}$ («слова в алфавите $\mathbf{N}$ ») снабжен геделевой нумерацией
$$(n_1,n_2,\dots ,n_k,\dots )\to 2^q{3}^{n_1-1}\dots p_{k+1}^{n_k-1}-1,$$

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

Проекции, диагональные отображения, отображения $V\to U\times V,v\mapsto$ $\mapsto (u_0,v)$ все вычислимы.

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

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

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

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

которые, по определению, всюду определенные вычислимые отображения $Q\to P$ такие, что если $q\mapsto p$, то $\overline{q}=\overline{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)\to R(U,W),(p,q)\mapsto r$$

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

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