3.1. Гёдель и Тьюринг

В главе 2 была предпринята попытка продемонстрировать мощь и строгий характер аргументации в пользу утверждения (обозначенного буквой ^), суть которого заключается в том, что математическое понимание не может являться результатом при­менения какого-либо осмысленно осознаваемого и полностью достоверного алгоритма (или, что то же самое, алгоритмов; см. возражение Q1). В приводимых рассуждениях, однако, ни словом не упомянуто еще об одной возможности, существенно более се­рьезной и ничуть не противоречащей утверждению <£, а имен­но: убежденность математика в истинности своих выводов может оказаться результатом применения им некоего неизвестного и неосознаваемого алгоритма, или же, возможно, математик при­меняет какой-то вполне постижимый алгоритм, однако при этом не может знать наверняка (или хотя бы искренне верить), что вы­воды его являются целиком и полностью результатом применения этого самого алгоритма. Ниже я покажу, что, хотя подобные до­пущения и вполне приемлемы с логической точки зрения, вряд ли их можно счесть хоть сколько-нибудь правдоподобными.

Прежде всего следует указать на то, что тщательно вы­страивая последовательности умозаключений (вполне, заметим, осознанных) с целью установления той или иной математиче­ской истины, математики вовсе не считают, что они лишь слепо следуют неким неосознаваемым правилам, будучи при этом не

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

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

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

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

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

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

Пояснение к используемым здесь обозначениям можно найти в §2.8. Впро­чем, G (F) без ущерба для смысла рассуждения можно было бы везде заменить на Г2 (F), в чем мы убедимся ниже.

Источник цитаты мне, к сожалению, обнаружить не удалось. Однако, как справедливо заметил Рихард Йожа, точная формулировка слов Фейнмана не имеет никакого значения, поскольку послание, которое они несут, применимо и к ним самим!

Как и ранее, обозначение G (F) можно без каких бы то ни было последствий заменить на П (F). То же справедливо и для комментариев к Q15—Q20.

Это означает, что при кодировании машины Тьюринга каждую последова­тельность ...110011… можно заменить на ...11011…В специ­фикации универсальной машины Тьюринга, описанной в НРК (см. примечание 7 после главы 2), имеется пятнадцать мест, где я этого не сделал. Решительно досадная оплошность с моей стороны, и это после того я приложил столько усилий для того, чтобы добиться (в рамках моих же собственных правил) по возможности наименьшего номера, определяющего эту универсальную машину. Упомянутая простая замена позволяет уменьшить мой номер более чем в 30000 раз! Я благодарен Стивену Ганхаусу за то, что он указал мне на этот недосмотр, а также за то, что он самостоятельно проверил всю представленную в НРК спе­цификацию и подтвердил, что она действительно определяет универсальную машину Тьюринга.

Более того, сам Тьюринг первоначально предполагал вообще останавли­вать машину всякий раз, когда она повторно переходит во внутреннее состо­яние «О» из любого другого состояния. В этом случае нам не только не пона­добилось бы вышеупомянутое ограничение, мы спокойно могли бы обойтись и без команды STOP. Тем самым мы достигли бы существенного упрощения, поскольку последовательность 11110 в качестве команды нам была бы уже не нужна, и ее можно было бы использовать как разделитель, что позволило бы избавиться от последовательности 111110. Это значительно сократило бы длину предписания K, и кроме того, вместо пятеричной системы счисления мы бы обошлись четверичной.

В главе 2 была предпринята попытка продемонстрировать мощь и строгий характер аргументации в пользу утверждения (обозначенного буквой ^), суть которого заключается в том, что математическое понимание не может являться результатом при­менения какого-либо осмысленно осознаваемого и полностью достоверного алгоритма (или, что то же самое, алгоритмов; см. возражение Q1). В приводимых рассуждениях, однако, ни словом не упомянуто еще об одной возможности, существенно более се­рьезной и ничуть не противоречащей утверждению <£, а имен­но: убежденность математика в истинности своих выводов может оказаться результатом применения им некоего неизвестного и неосознаваемого алгоритма, или же, возможно, математик при­меняет какой-то вполне постижимый алгоритм, однако при этом не может знать наверняка (или хотя бы искренне верить), что вы­воды его являются целиком и полностью результатом применения этого самого алгоритма. Ниже я покажу, что, хотя подобные до­пущения и вполне приемлемы с логической точки зрения, вряд ли их можно счесть хоть сколько-нибудь правдоподобными.

Прежде всего следует указать на то, что тщательно вы­страивая последовательности умозаключений (вполне, заметим, осознанных) с целью установления той или иной математиче­ской истины, математики вовсе не считают, что они лишь слепо следуют неким неосознаваемым правилам, будучи при этом не

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

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

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

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

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

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

Пояснение к используемым здесь обозначениям можно найти в §2.8. Впро­чем, G (F) без ущерба для смысла рассуждения можно было бы везде заменить на Г2 (F), в чем мы убедимся ниже.

Источник цитаты мне, к сожалению, обнаружить не удалось. Однако, как справедливо заметил Рихард Йожа, точная формулировка слов Фейнмана не имеет никакого значения, поскольку послание, которое они несут, применимо и к ним самим!

Как и ранее, обозначение G (F) можно без каких бы то ни было последствий заменить на П (F). То же справедливо и для комментариев к Q15—Q20.

Это означает, что при кодировании машины Тьюринга каждую последова­тельность ...110011… можно заменить на ...11011…В специ­фикации универсальной машины Тьюринга, описанной в НРК (см. примечание 7 после главы 2), имеется пятнадцать мест, где я этого не сделал. Решительно досадная оплошность с моей стороны, и это после того я приложил столько усилий для того, чтобы добиться (в рамках моих же собственных правил) по возможности наименьшего номера, определяющего эту универсальную машину. Упомянутая простая замена позволяет уменьшить мой номер более чем в 30000 раз! Я благодарен Стивену Ганхаусу за то, что он указал мне на этот недосмотр, а также за то, что он самостоятельно проверил всю представленную в НРК спе­цификацию и подтвердил, что она действительно определяет универсальную машину Тьюринга.

Более того, сам Тьюринг первоначально предполагал вообще останавли­вать машину всякий раз, когда она повторно переходит во внутреннее состо­яние «О» из любого другого состояния. В этом случае нам не только не пона­добилось бы вышеупомянутое ограничение, мы спокойно могли бы обойтись и без команды STOP. Тем самым мы достигли бы существенного упрощения, поскольку последовательность 11110 в качестве команды нам была бы уже не нужна, и ее можно было бы использовать как разделитель, что позволило бы избавиться от последовательности 111110. Это значительно сократило бы длину предписания K, и кроме того, вместо пятеричной системы счисления мы бы обошлись четверичной.