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

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

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

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

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

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

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

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

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