Количественная теория моделей вычислений имеет дело одновременно с измерениями протоколов по объему памяти и времени. В предшествующем подразделе рассматривалось время вычисления, здесь мы введем объем памяти. Для протоколов булевских схем (и машин Тьюринга) это сделать просто: длина каждой строки протокола объем памяти, требуемый в этот момент (плюс еще несколько битов для определения следующего гейта). Максимум этих длин — общий требуемый объем.

Случай нормальных моделей и бесконечных конструктивных миров — более интересный.

В общем случае мы будем называть функцией размера $U\to \mathbf{N}$ : $u\to |u|$ любую такую функцию, что для каждого $B\in \mathbf{N}$ есть только конечное число объектов, для которых $|u|⩽B$. Таким образом, число битов $|n|=[{\log }_{2}n]+1$ и тождественная функция $\Vert n\Vert =n$ — функции размера. Используя нумерацию, мы можем перевести их в любой конструктивный мир. В этих двух примерах число конструктивных объектов размера $⩽H$ растет как $\exp (cH)$ и, соответственно, $cH$. Такая оценка в более общих случаях позволяет делать различие между битовым размером, измеряющим длину описания объекта, и объемом объекта.

Как правило, требуется вычислимость функций размера. Тем не менее, есть исключения: например, колмогоровская сложность — невычислимая функция размера с очень важными свойствами (см. ниже и разд. 5).

Задав функцию размера (на всех релевантных мирах) и нормальную модель вычислений $\mathcal{S}$, мы можем рассмотреть следующие сложностные проблемы.
(А) Для заданного морфизма (вычислимого отображения) $f:U\to V$ оценить наименьший размер $K_{\mathcal{S}}(f)$ такой программы $p$, что $f=f_p$.

Колмогоров, Соломонов (Solomonoff) и Чайтин (Chaitin) доказали, что существует такая оптимальная универсальная модель вычислений $\mathcal{U}$, что для $P=\mathbf{N}$ и битовой функции размера для любой другой модели $\mathcal{S}$ существует такая константа $c$, что для любой функции $f$
$$K_{\mathcal{U}}(f)⩽K_{\mathcal{S}}(f)+c.$$

Когда модель $\mathcal{U}$ выбрана, $K_{\mathcal{U}}(f)$ называется колмогоровской сложностью функции $f$. Выбирая различным способом $\mathcal{U}$, мы будем получать одну и ту же функцию сложности с точностью до слагаемого порядка $O(1)$.

Эта мера сложности очень нетривиальна (и особенно интересна) для одноэлементного мира $U$ и бесконечного $V$. В этом случае она измеряет размер наиболее сжатого описания переменного конструктивного объекта в $V$. Эта мера сложности совершенно «объективна», так как почти не зависит от любых произвольных выборов. Будучи невычислимой, она не может быть непосредственно использована в компьютерной науке. Однако она накладывает некоторые основные ограничения на различные меры сложности, подобные ограничениям, задаваемым законами сохранения в физике.

Для $\mathbf{N}$ мы имеем $K_{\mathcal{U}}(n)⩽|n|+O(1)={\log }_2\Vert n\Vert +O(1)$. Первое неравенство «почти всегда» может быть заменено равенством, но бесконечно часто $K_{\mathcal{U}}(n)$ становится намного меньше, чем $|n|$.
(В) Для данного морфизма (рекурсивного отображения) $f:U\to V$ оценить время, требуемое для вычисления $f(u),u\in D(f)$ с использованием программы $р$ и сравнить результаты для различных р и различных моделей вычислений.
(C) Сделать то же самое для функиии «максимальный размер промежуточных конфигураций в протоколе вычисления $f(u)$ с использованием программы р» (зона, объем памяти).

В последних двух задачах следует сравнивать не числа, а функции: время и объем памяти в зависимости от размера входа. Здесь естественно возникает грубая полиномиальная шкала. Покажем, как это происходит.

Зафиксируем вычислительную модель $\mathcal{S}$ функцией перехода $s$, вычисляющей функции $U\to U$, и выберем функцию битового размера на $U$, удовлетворяющую следующему решающему предположению:
$(\bullet )|u|-c⩽|s_p(u)|⩽|u|+c$, где константа с может зависеть от $p$, но не зависит от и.
В этом случае мы имеем $|s_p^m(u)|⩽|u|+c_{p}m$, т. е. требуемый объем памяти растет со временем не более, чем линейно.

Пусть теперь ( ${\mathcal{S}}^{\prime },s^{\prime })$ — другая такая модель, что $s_p=s_q^{\prime }$ для некоторого $q$. Например, такое $q$ всегда существует, если ${\mathcal{S}}^{\prime }$ универсальна. Предположим, что $s^{\prime }$ также удовлетворяет и ($\cdot$) и, вдобавок,
($\cdot$$\cdot$) $s$ может быть вычислено в модели ${\mathcal{S}}^{\prime }$ за время, ограниченное полиномом $F$ в пределах объема памяти, занимаемого входными данными.

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

Тогда мы можем заменить одно применение $s_p$ к $s_p^m(u)$ на $⩽F(|u|+cm)$ применений $s_q^{\prime }$. И если нам нужно $T(u)$ шагов для того, чтобы вычислить $f_p(u)$ с использованием $\mathcal{S}$, нам надо не более, чем $⩽\sum _{m=1}^{T(u)}F(|u|+cm)$ шагов для вычисления той же самой функции с использованием ${\mathcal{S}}^{\prime }$ и $q$. В детализованной модели вычисления может учитываться добавочная стоимость слияния двух протоколов. Это пример перевода морфизма (4), поднятого до миров протоколов.

Таким образом, из ($\cdot$) и ($\cdot$$\cdot$) следует, что функции, вычислимые за полиномиальное время с помощью $\mathcal{S}$, обладают таким же свойством для любых разумных моделей. Заметим, что для любых таких функций выполнено неравенство $|f(u)|⩽G(|u|)$ для некоторого полинома $G$, а также область определения $D(f)$ такой функции разрешима: если за $T(|u|)s_p$-шагов мы не попали в заключительное состояние, то $uotinD(f)$.

Таким образом, мы можем определить класс $PF$ функций, например, типа ${\mathbf{N}}^k\to \mathbf{N}$, вычислимых за полиномиальное время с помощью фиксированной универсальной машины Тьюринга, и, используя вышеприведенную аргументацию, установить, что это определение не зависит от модели.

Однако, если мы хотим расширить его до конструктивной вселенной $\mathcal{C}$, нам придется постулировать вдобавок, что любой конструктивный мир $U$ задается совместно с естественным классом нумераций, которые вместе со своими обращениями вычислимы за полиномиальное время. Это похоже на часть содержания «полиномиального тезиса Чёрча», введенного М. Фридманом в [Fr1]. Если мы примем это усиление тезиса Чёрча, то мы можем определить также битовый размер любого конструктивного объекта как битовый размер его номера в одной из этих нумераций. Частное двух таких функций размера ограничено положительными константами сверху и снизу.

Ниже мы будем рассматривать только вселенные $\mathcal{C}$ и миры $U$ с этими свойствами и $|u|$ будет всегда обозначением одной из норм битового размера. Геделева нумерация (2) для $\mathbf{N}\times \mathbf{N}$ показывает, что такие $\mathcal{C}$ по-прежнему замкнуты относительно конечных произведений. (Заметим, однако, что красивая нумерация (3) для ${\mathbf{N}}^{\ast }$, использующая простые числа, не вычислима за полиномиальное время; ее можно заменить другой нумерацией, которая лежит в $PF$.)