Теперь мы готовы точно определить предельную длину предписания K, получаемого путем вышеприведенного построения, как функцию от длины алгоритма A. Сравним эту «длину» со «степенью сложности», определенной в §2.6 (в конце комментария к возражению Q8). Для некоторой конкретной машины Тьюринга T_m (например, той, что выполняет вычисление A) эта величина равна количеству знаков в двоичном представлении числа m. Для некоторого конкретного машинного действия T_m(n) (например, выполнения предписания K) эта величина равна количеству двоичных цифр в большем из чисел тип. Обозначим через α и κ количество двоичных цифр в a и k' соответственно, где

Поскольку алгоритм A содержит, как минимум, 2N - 1 команд (учитывая, что первую команду мы исключили) и поскольку для каждой команды требуется, по крайней мере, три двоичные цифры, общее число двоичных цифр в номере его машины Тьюринга а непременно должно удовлетворять условию

В вышеприведенном дополнительном списке команд для K есть 105 мест (справа от стрелок), где к имеющемуся там числу следует прибавить N. Все получаемые при этом числа не превышают N + 55, а потому их расширенные двоичные представления содержат не более 2 log₂(N + 55) цифр, в результате чего общее количество двоичных цифр, необходимых для дополнительного определения внутренних состояний, не превышает 210 log₂(N + 55). Сюда нужно добавить цифры, необходимые для добавочных символов 0, 1, R и L, что составляет еще 527 цифр (включая одну возможную добавочную «команду-пустышку» и учитывая, что мы можем исключить шесть символов 0 по правилу, согласно которому 00 можно представить в виде 0). Таким образом, для определения предписания K требуется больше двоичных цифр, чем для определения алгоритма A, однако разница между этими двумя величинами не превышает 527 + 210 log₂(N + 55):

Применив полученное выше соотношение α ≥ 6N - 6, получим (учитывая, что 210 log₂6 > 542)

Затем найдем степень сложности η конкретного вычисления C_k(k), получаемого посредством этой процедуры. Вспомним, что степень сложности машины T_m (n) определяется как количество двоичных цифр в большем из двух чисел m, n. В данной ситуации C_k = T_k, так что число двоичных цифр в числе «m» этого вычисления равно κ. Для того чтобы определить, сколько двоичных цифр содержит число «n» этого вычисления, рассмотрим ленту, содержащую вычисление C_k (k). Эта лента начинается с последовательности символов 111110, за которой следует двоичное выражение числа k', и завершается последовательностью 11011111. В соответствии с предложенным в НРК соглашением всю эту последовательность (без последней цифры) следует читать как двоичное число; эта операция дает нам номер «n», который присваивается ленте машины, выполняющей вычисление T_m(n). То есть число двоичных цифр в данном конкретном номере «n» равно κ + 13, и, следовательно, число κ + 13 совпадает также со степенью сложности ту вычисления C_k (k), благодаря чему мы можем записать η = κ + 13 < α — 2 + 210 log₂ (α + 336), или проще:

Детали вышеприведенного рассуждения специфичны для данного конкретного предложенного еще в НРК способа кодирования машин Тьюринга, и при использовании какого-либо иного кодирования они также будут несколько иными. Основная же идея очень проста. Более того, прими мы формализм λ- исчисления, вся операция оказалась бы, в некотором смысле, почти тривиальной. (Достаточно обстоятельное описание λ-исчисления Черча можно найти в НРК, конец главы 2; см. также [52].) Предположим, например, что алгоритм A определяется некоторым λ-оператором A, выполняющим действие над другими операторами P и Q, что выражается в виде операции (AP)Q. Оператором P здесь представлено вычисление C_p, а оператором Q — число q. Далее, оператор A должен удовлетворять известному требованию, согласно которому для любых P и Q должно быть истинным следующее утверждение:

Мы без труда можем составить такую операцию λ-исчисления, которая не завершается, однако этот факт невозможно установить посредством оператора A. Например, положим

т.е. KY = (AY)Y для любого оператора Y. Затем рассмотрим λ-операцию