Эпифеномен — побочное явление, сопутствующее другим явлениям (феноменам), но не оказывающее на них никакого влияния. — Прим. перев.

Напомним, что здесь и далее приводятся страницы оригинального английского издания. — Прим. перев.

Время от времени математики натыкаются на процедуру, которая «очевидно» алгоритмична по своей природе, пусть даже порой не всегда бывает ясно, как эту процедуру можно сформулировать в виде операций машины Тьюринга или лямбда-исчисления. В таких случаях можно утверждать, что, «согласно тезису Черча», такая операция и в самом деле должна существовать. См., например, [67]. В этом пути нет ничего зазорного, и, уж конечно, не возникает никакого противоречия с C. Более того, на таком толковании тезиса Черча основывается большая часть рассуждений главы 3.

В черновом варианте книги слова «извилистой» здесь не было. Если шары расположены точно на прямой линии, этот трюк оказывается достаточно простым: я узнал об этом, к своему удивлению, когда попробовал проделать это сам. При расстановке шаров по прямой возникает неожиданная устойчивость, отсутствующая в общем случае.

Необходимо отметить, что это равенство не является истинным для различных странных «чисел», встречающихся порой в математике, — например, для трансфинитных чисел, о которых упоминается в пояснении к Q19, §2.10. Однако для натуральных чисел, о которых здесь, собственно, и идет речь, оно всегда справедливо.

Здесь я предполагаю, что если процедура А вообще завершается, то это свидетельствует об успешном установлении факта незавершаемости C (n). Если же А «застревает» по какой-либо иной, нежели достижение «успеха», причине, то это означает, что в данном случае процедура A корректно завершиться не может. См. далее по тексту возражения Q3 и Q4, а также Приложение А.

Собственно, точно такой же результат достигается посредством процедуры, выполняемой универсальной машиной Тьюринга над парой чисел q, n; см. Приложение А и НРК, с. 51-57.

Термин «алгоритмизм», который (по своей сути) прекрасно подходит для обозначения «точки зрения A» в моей классификации, был предложен Хао Ваном [377].

Приведение к абсурду (лат.), доказательство от противного. — Прим. перев.

Чтобы подчеркнуть, что я принимаю это обстоятельство во внимание, я отсылаю читателя к Приложению А, где представлена явная вычислительная процедура (выполненная в соответствии с правилами, подробно описанными в НРК, глава 2) для получения операции C_k(k) машины Тьюринга посредством алгоритма A. Здесь предполагается, что алгоритм A задан в виде машины Тьюринга T_a. определение же вычисления C_q(n) кодируется как операция машины T_a над числом q, а затем над числом n.

Представление некоторых формальных систем включает в себя бесконечное количество аксиом (они описываются через посредство структур, называемых «схемами аксиом»), однако, чтобы оставаться «формальной» в том смысле, какой вкладываю в это понятие я, система должна быть выразима в каком-то конечном виде — например, упомянутая система с бесконечным количеством аксиом должна порождаться