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

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

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

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

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

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

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

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

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

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

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

Пусть теперь ( $\left.\mathcal{S}^{\prime}, s^{\prime}\right)$ – другая такая модель, что $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)$ на $\leqslant F(|u|+c m)$ применений $s_{q}^{\prime}$. И если нам нужно $T(u)$ шагов для того, чтобы вычислить $f_{p}(u)$ с использованием $\mathcal{S}$, нам надо не более, чем $\leqslant \sum_{m=1}^{T(u)} F(|u|+c m)$ шагов для вычисления той же самой функции с использованием $\mathcal{S}^{\prime}$ и $q$. В детализованной модели вычисления может учитываться добавочная стоимость слияния двух протоколов. Это пример перевода морфизма (4), поднятого до миров протоколов.

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

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

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

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