В этом разделе я рассматриваю только детерминированные вычисления, которые могут быть промоделированы классическими динамическими системами с дискретным временем и впоследствии представлены на квантовом уровне.

Алан Тьюринг предложил микроскопический анализ интуитивной идеи алгоритмического вычисления. В некотором смысле он нашел его генетический код. Атом информации – один бит, можно подобрать атомарные операции, действующие на одном/двух битах и выдающие результаты такого же малого размера. Наконец, последовательность операций строго детерминирована локальным устройством, размер которого ограничен также несколькими битами.

Для разнообразия я пойду в обратном направлении и начну этот раздел с представления макрокосма классической теории вычислений. Для этого подходит язык теории категорий.

Пусть $\mathscr{C}$ – категория, объекты которой – вычислимые или конечные множества $U$. Элементы $x$ этих множеств будут в общем случае конечными множествами с дополнительной структурой. Не ожидая появления всех необходимых аксиом, мы назовем $x \in U$ конструктивным объектом типа $U$ (целое число, конечный граф, слово в данном алфавите, булево выражение, пример массовой проблемы … ). Множество $U$ само будет называться конструктивным миром объектов фиксированного типа, а $\mathscr{C}$ – конструктивной вселенной. Категория $\mathscr{C}$, которая будет сделана более конкретной ниже, будет содержать все конечные произведения и конечные объединения своих объектов, а также конечные множества $U$ всех мощностей.

Морфизмы $U \rightarrow V$ в $\mathscr{C}$ – некоторые частичные отображения соответствующих множеств. Более точно, такой морфизм – пара $(D(f), f)$, где $D(f) \subset U$ и $f: D(f) \rightarrow V$ – отображение множеств. Композиция определяется равенством
\[
(D(g), g) \circ(D(f), f)=\left(g^{-1} D(f), g \circ f\right) .
\]

Мы будем опускать $D(f)$, когда это не приводит к двусмысленности.
Морфизмы $f$, которые мы будем рассматривать, – (полу)вычислимые функции $U \rightarrow V$. Интуитивный смысл этого понятия, которое имеет очень сильный эвристический потенциал, может быть объяснен так: должен существовать алгоритм $\varphi$ такой, что если взять в качестве входа конструктивный объект $u \in U$, то выполняется одна из трех возможностей:
(i) $u \in D(f), \varphi$ выдает за конечное число шагов результат $f(u) \in V$.
(ii) $u
otin D(f), \varphi$ выдает за конечное число шагов стандартный результат, обозначающий НЕТ.
(iii) $u
otin D(f), \varphi$ работает бесконечно долго без выдачи какого-либо результата.

Необходимость включения альтернативы (iii) в определение (полу)вычислимости было важным и нетривиальным открытием классической теории. Множество всех морфизмов $U \rightarrow V$ обозначается $\mathscr{C}(U, V)$.

Множества вида $D(f) \subset U$ называются перечислимыми множествами $U$. Если как $E \subset U$, так и $U \backslash E$ перечислимы, то $E$ называется разрешимым.

Классическая теория вычислений делает все это более точным следующим образом.