Текст книги "Тени разума. В поисках науки о сознании"

Автор книги: Роджер Пенроуз

сообщить о нарушении

Текущая страница: 14 (всего у книги 49 страниц)

Многие ошибочно полагают (в духе приведенных в возражении Q16соображений), что из теоремы Гёделя следует существование множества различных арифметик, каждая из которых в равной степени обоснованна. Соответственно, та частная арифметика, которую мы, возможно, по чистой случайности избрали для своих нужд, определяется просто какой-то произвольно взятой формальной системой. В действительности же теорема Гёделя показывает, что ни одна из этих формальных систем (будучи непротиворечивой) не может быть полной; поэтому (как доказывается далее) к ней можно непрерывно добавлять какие угодно новые аксиомы и получать всевозможные альтернативные непротиворечивые системы, которыми при желании можно заменить ту, в рамках которой мы работаем в настоящий момент. Эту ситуацию нередко сравнивают с той, что сложилась некогда с евклидовой геометрией. На протяжении двадцати одного века люди верили, что евклидова геометрия является единственно возможной геометрией. Но когда в восемнадцатом веке сразу несколько великих математиков (таких как Гаусс, Лобачевский и Бойяи) показали, что существуют в равной степени возможные альтернативы общепринятой геометрии, геометрии пришлось отступить с абсолютных позиций на произвольные. Нередко можно услышать, будто Гёдель показал, что арифметика так же представляет собой предмет произвольного выбора, при этом один набор непротиворечивых аксиом оказывается ничуть не хуже любого другого.

Однако подобная интерпретация того, что доказал Гёдель, абсолютно неверна. Согласно Гёделю, само по себе понятие формальной системы аксиом не подходит для передачи даже самых элементарных математических понятий. Когда мы употребляем термин «арифметика» без дальнейших пояснений, мы подразумеваем обычную арифметику, которая работает с обычными натуральными числами 0, 1, 2, 3, 4, … (и, быть может, с их отрицаниями), а вовсе не со «сверхнатуральными» числами, что бы это понятие ни означало. Мы можем, если пожелаем, исследовать свойства формальных систем, и это, конечно же, станет ценным вкладом в процесс математического познания. Однако такое предприятие несколько отличается от исследования обычных свойств обычных натуральных чисел. В некотором отношении данная ситуация весьма напоминает ту, что сложилась в последнее время с геометрией. Изучение неевклидовых геометрий интересно с математической точки зрения, да и сами геометрии имеют ряд важных областей применения (например, в физике, см. НРК, глава 5, особенно рис. 5.1 и 5.2, а также §4.4), но, когда термин «геометрия» используется в обычном языке (в отличие от «жаргона» математиков или физиков-теоретиков), подразумевается, как правило, обычная евклидова геометрия. Однако имеется и разница: то, что логик может назвать «евклидовой геометрией», действительно можно определить (с некоторыми оговорками ^{34} ) через определенную формальную систему, тогда как обычную «арифметику», как показал Гёдель, определить таким образом нельзя.

Гёдель доказал не то, что математика (в особенности арифметика) – это произвольные поиски, направление которых определяется прихотью Человека; он доказал, что математика – это нечто абсолютное, и в ней мы должны не изобретать, но открывать (см. §1.17). Мы открываем, что такое натуральные числа и без труда отличаем их от любых сверхнатуральных чисел. Гёдель показал, что ни одна система «искусственных» правил не способна сделать это за нас. Такая платоническая точка зрения была существенна для Гёделя, не менее существенной она будет и для нас в последующих рассуждениях ( §8.7).

Q17. Допустим, что формальная система F предназначена для представления тех математических истин, что в принципе доступны человеческому разуму. Не можем ли мы обойти проблему невозможности формального включения в систему Fгёделевского высказывания G( F), включив вместо него что-либо, имеющее смысл G( F), воспользовавшись при этом новой интерпретацией смысла символов системы F?

Определенные способы представления примененного к Fгёделевского доказательства в рамках формальной системы F (достаточно обширной) действительно существуют, коль скоро новый, реинтерпретированный, смысл символов системы F полагается отличным от исходного смысла символов этой системы. Однако если мы пытаемся таким образом интерпретировать систему F какпроцедуру, с помощью которой разум приходит к тем или иным математическим выводам, то подобный подход является не чем иным, как шулерством. Если мы намерены толковать мыслительную деятельность исключительно в рамках системы F, то ее символы не должны изменять свой смысл «на полпути». Если же мы принимаем, что мыслительная деятельность может содержать что-то помимо операций самой системы F– т.е. изменение смысла символов, – то нам необходимо знать и правила, управляющие подробным изменением. Либо эти правила окажутся неалгоритмическими, и это сыграет в пользу G, либо для них найдется какая-то конкретная алгоритмическая процедура, и тогда нам следовало бы изначально включить этупроцедуру в нашу «систему F» – обозначим ее через F ^†– с тем, чтобы она представляла собой полную совокупность процедур, обусловливающих наши с вами понимание и проницательность, а значит, необходимости в изменении смысла символов не возникло бы вовсе. В последнем случае вместо гёделевского высказывания G( F) из предыдущего рассуждения нам предстоит разбираться уже с высказыванием G( F ^†), так что ничего мы в результате не выигрываем.

Q18. Даже в такой простой системе, как арифметика Пеано, можно сформулировать теорему, интерпретация которой имеет следующий смысл:

«система Fобоснованна», а следовательно, «высказывание G( F) истинно».

Разве это не все, что нам нужно от теоремы Гёделя? Значит, теперь, полагая обоснованной какую угодно формальную систему F, мы вполне можем поверить и в истинность ее гёделевского высказывания – при условии, разумеется, что мы готовы принять арифметику Пеано, разве не так?

Подобную теорему ^{35} действительно можно сформулировать в рамках арифметики Пеано. Точнее (поскольку мы не можем в пределах какой бы то ни было формальной системы должным образом выразить понятие «обоснованности» или «истинности», как это следует из знаменитой теоремы Тарского), мы, в сущности, формулируем более сильный результат:

«система Fнепротиворечива», а следовательно, «высказывание G( F) истинно»,

либо иначе:

«система F ω-непротиворечива», а следовательно, «высказывание Ω( F) истинно».

Из этих высказываний следует вывод, необходимый для Q18, поскольку если система Fобоснованна, то она, разумеется, непротиворечива или омега-непротиворечива, в зависимости от обстоятельств. Понимая смыслприсутствующего здесь символизма, мы и в самом деле можем поверить в истинность высказывания G( F) на основании одной лишь веры в обоснованность системы F. Это, впрочем, мы уже приняли. Если понимать смысл, то действительно возможно перейти от Fк G( F). Сложности возникнут лишь в том случае, если нам вздумается исключить необходимость интерпретаций и сделать переход от Fк G( F)  автоматическим. Будь это возможно, мы смогли бы автоматизировать общую процедуру «гёделизации» и создать алгоритмическое устройство, которое действительно будет содержать в себе все, что нам нужно от теоремы Гёделя. Однако такой возможности у нас нет – захоти мы добавить эту предполагаемую алгоритмическую процедуру в какую угодно формальную систему F, выбранную нами в качестве отправной, в результате просто-напросто получилась бы, по сути, некоторая новая формальная система F ^#, а ее гёделевское высказывание G( F ^#) оказалось бы уже за ее рамками. Таким образом, согласно теореме Гёделя, какой-тоаспект понимания всегда остается «за нами», независимо от того, какая доля его оказалась включена в формализованную или алгоритмическую процедуру. Это «гёделево понимание» требует постоянного соотнесения с действительным смыслом символов какой бы то ни было формальной системы, к которой применяется процедура Гёделя. В этом смысле ошибка Q18весьма похожа на ту, что мы обнаружили, комментируя возражение Q17. С невозможностью автоматизации процедуры гёделизации тесно связаны также рассуждения по поводу Q6и Q19.

В возражении Q18присутствует еще один аспект, который стоит рассмотреть. Представим себе, что у нас есть обоснованная формальная система H, содержащая арифметику Пеано. Теорема, о которой говорилось в Q18, окажется среди следствий системы H, а частным ее примером, применимым к конкретной системе F(т.е., собственно, H), будет теорема системы H. Таким образом, можно сформулировать один из выводов формальной системы H:

«система  Hобоснованна», а следовательно, «высказывание G( H) истинно»;

или, точнее, скажем так:

«система  Hнепротиворечива», а следовательно, «высказывание G( H) истинно».

Если говорить о реальном смысле этих утверждений, то из них, в сущности, следует, что высказывание G( H) также утверждается системой. А так как (что касается первого из двух вышеприведенных утверждений) истинность любогопроизводимого системой Hутверждения, во всяком случае, обусловлена допущением, что система Hобоснованна, то получается, что если система Hутверждает нечто, явно обусловленное ее собственной обоснованностью, то она вполне может утверждать это напрямую. (Из утверждения «если мне можно верить, то  Xистинно» следует более простое утверждение, исходящее из того же источника: « Xистинно».) Однако в действительности обоснованная формальная система H не можетутверждать истинность высказывания G( H), что является следствием ее неспособности утверждать собственную обоснованность. Более того, как мы видим, она не может включать в себя и смысл символов, которыми оперирует. Те же факты годятся и для иллюстрации второго утверждения, причем в этом случае ко всему прочему добавляется и некоторая ирония: система Hне способна утверждать собственную непротиворечивость лишь в том случае, если она  действительнонепротиворечива, если же формальная система непротиворечивой не является, то подобные ограничения ей неведомы. Противоречивая формальная система Hможет утверждать (в качестве «теоремы») вообще все, что она в состоянии сформулировать! Она вполне может, как выясняется, сформулировать и утверждение: «система М. непротиворечива». Формальная система (достаточно обширная) утверждает собственную непротиворечивость тогда и только тогда, когда она противоречива!

Q19. Почему бы нам просто не учредить процедуру многократного добавления высказывания G( F) к любой системе F, какой мы в данным момент пользуемся, и не позволить этой процедуре выполняться бесконечно?

Когда нам дана какая-либо конкретная формальная система F, достаточно обширная и полагаемая обоснованной, мы в состоянии понять, как добавить к ней высказывание G( F) в качестве новой аксиомы и получить тем самым новую систему F ₁, которая также будет считаться обоснованной. (Для согласования обозначений в последующем изложении систему Fможно также обозначить через F ₀.) Теперь мы можем добавить к системе F ₁высказывание G( F ₁), получив в результате новую систему F ₂, также, предположительно, обоснованную. Повторив данную процедуру, т.е. добавив к системе F ₂высказывание G( F ₂), получим систему F ₃и т.д. Приложив еще совсем немного усилий, мы непременно сообразим, как построить еще одну формальную систему F _ω , аксиомы которой позволят нам включить в систему в качестве дополнительных аксиом для Fвсе бесконечное множество высказываний { G( F ₀), G( F ₁), G( F ₂), G( F ₃), …}. Очевидно, что система F _ω также будет обоснованной. Этот процесс можно продолжить и дальше: к системе F _ω добавляется высказывание G( F _ω ), в результате чего получается система F _ω+1, к которой затем добавляется высказывание G( F _ω+1), что дает систему F _ω+2, и т.д. Далее, как и в предыдущий раз, мы можем построить формальную систему F _ω2(= F _{ω+ ω}), включив в нее весь бесконечный набор соответствующих аксиом, каковая система опять-таки окажется очевидно обоснованной. Добавлением к ней высказывания G( F _ω2), получим систему F _ω2+1и т.д., а потом построим новую систему F _ω3(= F _{ω2+ ω}), включив в нее опять-таки бесконечное множество аксиом. Повторив всю вышеописанную процедуру, мы сможем получить формальную систему F _ω4, после следующего повтора – систему F _ω5и т.д. Еще чуть-чуть потрудиться, и мы обязательно увидим, как можно включить уже этомножество новых аксиом { G( F _ω ), G( F _ω2), G( F _ω3), G( F _ω4), …} в новую формальную систему F _{ω ²} (= F _ωω ). Повторив всю процедуру, мы получим новую систему F _{ω ²+ ω ²}, затем – систему F _{ω ²+ ω ²+ ω ²}и т.д.; в конце концов, когда мы сообразим, как связать все этовместе (разумеется, и на этот раз не без некоторого напряжения умственных способностей), наши старания приведут нас к еще более всеобъемлющей системе F _{ω ³} , которая также должна быть обоснованной.

Читатели, которые знакомы с понятием канторовых  трансфинитных ординалов, несомненно, узнают индексы, обычно используемые для обозначения таких чисел. Тем же, кто от подобных вещей далек, не стоит беспокоиться из-за незнания точного значения этих символов. Достаточно сказать, что описанную процедуру «гёделизации» можно продолжить и далее: мы получим формальные системы F _{ω ⁴} , F _{ω ⁵} , …, после чего придем к еще более обширной системе F _{ω ^ω} , затем процесс продолжается до еще больших ординалов, например, ω ^{ω ω}и т.д. – до тех пор, пока мы все еще способны на каждом последующем этапе понять, каким образом систематизировать все множество гёделизаций, которые мы получили на данный момент. В этом и заключается основная проблема: для упомянутых нами «усилий, трудов и напряжений» требуется соответствующее понимание того, как должно систематизировать предыдущие гёделизаций. Эта систематизация выполнима при условии, что достигаемый к каждому последующему моменту этап будет помечаться так называемым рекурсивнымординалом, что, в сущности, означает, что должен существовать определенный алгоритм, способный такую процедуру генерировать. Однако алгоритмической процедуры, которую можно было бы заложить заранее и которая позволила бы выполнить описанную систематизацию для всех рекурсивных ординалов раз и навсегда, просто-напросто не существует. Нам снова неизбежно потребуется понимание.

Вышеприведенная процедура была впервые предложена Аланом Тьюрингом в его докторской диссертации (а опубликована в [ 368]) ^{36} ; там же Тьюринг показал, что любоеистинное Π ₁-высказывание можно, в некотором смысле, доказать с помощью многократной гёделизаций, подобной описанной нами. (См. также [ 117].) Впрочем, воспользоваться этим для получения механической процедуры установления истинности Π ₁-высказываний нам не удастся по той простой причине, что механически систематизировать гёделизацию невозможно. Более того, невозможность «автоматизации» процедуры гёделизаций как раз и выводитсяиз результата Тьюринга. А в §2.5мы уже показали, что общее установление истинности (либо ложности) Π ₁-высказываний невозможно произвести с помощью каких бы то ни было алгоритмических процедур. Так что в поисках систематической процедуры, не доступной тем вычислительным соображениям, которые мы рассматривали до настоящего момента, многократная гёделизация нам ничем помочь не сможет. Таким образом, для вывода  Gвозражение Q19угрозы не представляет.

Q20. Реальная ценность математического понимания состоит, безусловно, не в том, что благодаря ему мы способны выполнять невычислимые действия, а в том, что оно позволяет нам заменить невероятно сложные вычисления сравнительно простым пониманием. Иными словами, разве не правда, что, используя разум, мы, скорее, «срезаем углы» в смысле теории сложности, а вовсе не «выскакиваем» за пределы вычислимого?

Я вполне готов поверить в то, что на практикеинтуиция математика гораздо чаще используется для «обхода» вычислительной сложности, чем невычислимости. Как-никак математики по природе своей склонны к лени, а потому зачастую стараются изыскать всяческие способы избежать вычислений (пусть даже им придется в итоге выполнить значительно более сложную мыслительную работу, нежели потребовало бы собственно вычисление). Часто случается так, что попытки заставить компьютеры бездумно штамповать теоремы даже умеренно сложных формальных систем быстро загоняют эти самые компьютеры в ловушку фактически безнадежной вычислительной сложности, тогда как математик-человек, вооруженный пониманием смысла, лежащего в основе правил такой системы, без особого труда получит в рамках этой системы множество интересных результатов ^{37} .

Причина того, что в своих доказательствах я рассматривал не сложность, а невычислимость, заключается в том, что только с помощью последней мне удалось сформулировать необходимые для доказательства сильные утверждения. Не исключено, что в работе большинства математиков вопросы невычислимости играют весьма незначительную роль, если вообще играют. Однако суть не в этом. Я глубоко убежден, что понимание (в частности, математическое) представляет собой нечто, недоступное вычислению, а одной из немногих возможностей вообще подступиться ко всем этим вопросам является как раз доказательство Гёделя(—Тьюринга). Никто не отрицает, что наши математические интуиция и понимание нередко используются для получения результатов, достижимых, в принципе, и вычислительным путем, – но и здесь слепое, не отягощенное пониманием, вычисление может оказаться неэффективным настолько, что попросту не будет работать (см. §3.26). Однако рассмотрение всех таких случаев представляется мне неизмеримо более сложным подходом, нежели обращение к общей невычислимости.

Как бы то ни было, высказанные в возражении Q20 соображения, пусть и справедливые, все же ни в коей мере не противоречат выводу G.

Приложение A: Гёделизирующая машина Тьюринга в явном виде

Допустим, что у нас имеется некая алгоритмическая процедура A, которая, как нам известно, корректно устанавливает незавершаемость тех или иных вычислений. Мы получим вполне явную процедуру для построения на основе процедуры  A конкретного вычисления C, для которого  Aоказывается неадекватной; при этом мы сможем убедиться, что вычисление  C действительно незавершается. Приняв это явное выражение для C, мы сможем определить степень его сложности и сравнить ее со сложностью процедуры A, чего требуют аргументы §2.6 (возражение Q8) и §3.20.

Для определенности я воспользуюсь спецификациями той конкретной машины Тьюринга, которую я описал в НРК. Подробное описание этих спецификаций читатель сможет найти в названной работе. Здесь же я дам лишь краткое описание, которого вполне должно хватить для наших настоящих целей.

Машина Тьюринга имеет конечное число внутренних состояний, но производит все операции на бесконечной ленте. Эта лента представляет собой линейную последовательность «ячеек», причем каждая ячейка может быть маркированной или пустой, а общее количество отметок на ленте – величина конечная. Обозначим каждую маркированную ячейку символом 1, а каждую пустую ячейку – 0. В машине Тьюринга имеется также считывающее устройство, которое поочередно рассматривает отметки и, в явной зависимости от внутреннего состояния машины Тьюринга и характера рассматриваемой в данный момент отметки, определяет дальнейшие действия машины по следующим трем пунктам: (I) следует ли изменить рассматриваемую в данный момент отметку; (II) каким будет новое внутреннее состояние машины; (III) должно ли устройство сдвинуться по ленте на один шаг вправо (обозначим это действие через R) или влево (обозначим через L), или же на один шаг вправо с остановкой машины ( STOP). Когда машина, в конце концов, остановится, на ленте слева от считывающего устройства будет представлен в виде последовательности символов 0и 1ответ на выполненное ею вычисление. Изначально лента должна быть абсолютно чистой, за исключением отметок, описывающих исходные данные (в виде конечной строки символов 1и 0), над которыми машина и будет выполнять свои операции. Считывающее устройство в начале работы располагается слева от всех отметок.

При представлении на ленте натуральных чисел (будь то входные или выходные данные) иногда удобнее использовать так называемую расширенную двоичнуюзапись, согласно которой число, в сущности, записывается в обычной двоичной системе счисления, только двоичный знак «1» представляется символами 10, а двоичный знак «0» – символом 0. Таким образом, мы получаем следующую схему перевода десятичных чисел в расширенные двоичные:

0 ↔ 0

1 ↔ 10

2 ↔ 100

3 ↔ 1010

4 ↔ 1000

5 ↔ 10010

6 ↔ 10100

7 ↔ 101010

8 ↔ 10000

9 ↔ 100010

10 ↔ 100100

11 ↔ 1001010

12 ↔ 101000

13 ↔ 1010010

14 ↔ 1010100

15 ↔ 10101010

16 ↔ 100000

17 ↔ 1000010

и т.д.

Заметим, что в расширенной двоичной записи символы 1никогда не встречаются рядом. Таким образом, последовательность из двух или более 1вполне может послужить сигналом о начале и конце записи натурального числа. То есть для записи всевозможных команд на ленте мы можем использовать последовательности типа 110, 1110, 11110и т.д.

Отметки на ленте также можно использовать для спецификации конкретных машин Тьюринга. Это необходимо, когда мы рассматриваем работу универсальноймашины Тьюринга U. Универсальная машина Uработает с лентой, начальная часть которой содержит подробную спецификацию некоторой конкретной машины Тьюринга T, которую универсальной машине предстоит смоделировать. Данные, с которыми должна работать сама машина T, подаются в Uвслед за тем участком ленты, который определяет машину T. Для спецификации машины Tможно использовать последовательности 110, 1110и 11110, которые будут обозначать, соответственно, различные команды для считывающего устройства машины T, например: переместиться по ленте на один шаг вправо, на один шаг влево, либо остановиться, сдвинувшись на один шаг вправо:

R↔ 110

L↔ 1110

STOP ↔ 11110.

Каждой такой команде предшествует либо символ 0, либо последовательность 10, что означает, что считывающее устройство должно пометить ленту, соответственно, либо символом 0, либо 1, заменив тот символ, который оно только что считало. Непосредственно перед вышеупомянутыми 0или 10 располагается расширенное двоичное выражение числа, описывающего следующее внутреннее состояние, в которое должна перейти машина Тьюринга согласно этой самой команде. (Отметим, что внутренние состояния, поскольку количество их конечно, можно обозначать последовательными натуральными числами 0, 1, 2, 3, 4, 5, 6, …, N. При кодировании на ленте для обозначения этих чисел будет использоваться расширенная двоичная запись.)

Конкретная команда, к которой относится данная операция, определяется внутренним состоянием машины перед началом считывания ленты и собственно символами 0или 1, которые наше устройство при следующем шаге считает и, возможно, изменит. Например, частью описания машины  T может оказаться команда 23 0→ 17 1R, что означает следующее: «Если машина Tнаходится во внутреннем состоянии 23, а считывающее устройство встречает на ленте символ 0, то его следует заменить символом 1, перейти во внутреннее состояние 17 и переместиться по ленте на один шаг вправо». В этом случае часть «17 1R» данной команды будет кодироваться последовательностью 100001010110. Разбив ее на участки 1000010.10.110, мы видим, что первый из них представляет собой расширенную двоичную запись числа 17, второй кодирует отметку 1на ленте, а третий – команду «переместиться на шаг вправо». А как нам описать предыдущее внутреннее состояние (в данном случае 23) и считываемую в соответствующий момент отметку на ленте (в данном случае 0)? При желании можно задать их так же явно с помощью расширенной двоичной записи. Однако на самом деле в этом нет необходимости, поскольку для этого будет достаточно упорядочить различные команды в виде цифровой последовательности (например, такой: 0 0→, 0 1→, 1 0→, 1 1→, 2 0→, 2 1→, 3 0→, …).

К этому, в сущности, и сводится все кодирование машин Тьюринга, предложенное в НРК, однако для завершенности картины необходимо добавить еще несколько пунктов. Прежде всего, следует проследить за тем, чтобы каждому внутреннему состоянию, действующему на отметки 0и 1(не забывая, впрочем, о том, что команда для внутреннего состояния с наибольшим номером, действующая на 1, оказывается необходимой не всегда), была сопоставлена какая-либо команда. Если та или иная команда вообще не используется в программе, то необходимо заменить ее «пустышкой». Предположим, например, что в ходе выполнения программы внутреннему состоянию 23 нигде не придется сталкиваться с отметкой 1– соответствующая команда-пустышка в этом случае может иметь следующий вид: 23 1→ 0 0R.

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


[Закрыть]. Машина Тьюринга начинает работу, находясь во внутреннем состоянии 0; считывающее устройство движется по ленте, сохраняя это внутреннее состояние до тех пор, пока не встретит первый символ 1. Это обусловлено допущением, что в набор команд машины Тьюринга всегда входит операция 0 0→ 0 0R. Таким образом, в действительной спецификации машины Тьюринга в виде последовательности 0и 1явного задания этой команды не требуется; вместо этого мы начнем с команды 0 1→ X, где Xобозначает первую нетривиальную операцию запущенной машины, т.е. первый символ 1, встретившийся ей на ленте. Это значит, что начальную последовательность 110(команду → 0 0R), которая в противном случае непременно присутствовала бы в определяющей машину Тьюринга последовательности, можно спокойно удалить. Более того, в такой спецификации мы будем всегда удалять и завершающую последовательность 110, так как она одинакова для всех машин Тьюринга.

Получаемая в результате последовательность символов 0и 1представляет собой самую обыкновенную (т.е. нерасширенную) двоичную запись номера машины Тьюринга nдля данной машины (см. главу 2 НРК). Мы называем ее n-й машиной Тьюринга и обозначаем  T= T _n. Каждый такой двоичный номер (с добавлением в конце последовательности 110) есть последовательность символов 0и 1, в которой нигде не встречается более четырех 1подряд. Номер n, не удовлетворяющий данному условию, определяет «фиктивную машину Тьюринга», которая прекратит работать, как только встретит «команду», содержащую более четырех 1. Такую машину « T _n» мы будем называть некорректно определенной. Ее работа с какой угодно лентой является по определениюнезавершающейся. Аналогично, если действующая машина Тьюринга встретит команду перехода в состояние, определенное числом, большим всех тех чисел, для которых были явно заданы возможные последующие действия, то она также «зависнет»: такую машину мы будем полагать «фиктивной», а ее работу – незавершающейся. (Всех этих неудобств можно без особого труда избежать с помощью тех или иных технических средств, однако реальной необходимости в этом нет; см. §2.6, Q4).

Для того чтобы понять, как на основе заданного алгоритма  Aпостроить явное незавершающееся вычисление, факт незавершаемости которого посредством алгоритма Aустановить невозможно, необходимо предположить, что алгоритм Aзадан в виде машины Тьюринга. Эта машина работает с лентой, на которой кодируются два натуральных числа  pи q. Мы полагаем, что если завершается вычисление A( p, q), то вычисление, производимое машиной  T _pс числом q, незавершается вовсе. Вспомним, что если машина T _pопределена некорректно, то ее работа с числом qне завершается, каким бы это самое qни было. В случае такого «запрещенного»  pисход вычисления A( p, q) может, согласно исходным допущениям, быть каким угодно. Соответственно, нас будут интересовать исключительно те числа p, для которых машина T _pопределена корректно. Таким образом, в записанном на ленте двоичном выражении числа  pпяти символов 1подряд содержаться не может. Значит, для обозначения на ленте начала и конца числа  pмы вполне можем воспользоваться последовательностью 11111.

То же самое, очевидно, необходимо сделать и для числа q, причем оно вовсе необязательно должно быть числом того же типа, что и p. Здесь перед нами возникает техническая проблема, связанная с чрезвычайной громоздкостью машинных предписаний в том виде, в каком они представлены в НРК. Удобным решением этой проблемы может стать запись чисел pи  qв  пятеричнойсистеме счисления. (В этой системе запись «10» означает число пять, «100» – двадцать пять, «44» – двадцать четыреи т.д.) Однако вместо пятеричных цифр 0, 1, 2, 3 и 4 я воспользуюсь соответствующими последовательностями символов на ленте 0,10,110,1110 и 11110. Таким образом, мы будем записывать

0 как 0

1 как  10

2 как 110

3 как 1110

4 как 11110

5 как 100

6 как 1010

7 как 10110

8 как 101110

9 как 1011110

10 как 1100

11 как 11010

12 как 110110

13 как 1101110

14 как 11011110

15 как 11100

16 как 111010

…

25 как 1000

26 как 10010

и т.д.

Под « C _p» здесь будет пониматься вычисление, выполняемое корректно определенной машиной Тьюринга T _r, где  rесть число, обыкновенное двоичное выражение которого (с добавлением в конце последовательности символов 110) в точности совпадает с числом  pв нашей пятеричной записи. Число q, над которым производится вычисление C _p, также необходимо представлять в пятеричном выражении. Вычисление же A( p, q) задается в виде машины Тьюринга, выполняющей действие с лентой, на которой кодируется пара чисел p, q. Запись на ленте будет выглядеть следующим образом:

… 00111110p111110q11111000…,

где  pи  qсуть вышеописанные пятеричные выражения чисел, соответственно,  pи q.

Требуется отыскать такие числа pи q, для которых не завершается не только вычисление C _p( q), но и вычисление A( p, q). Процедура из §2.5позволяет сделать это посредством отыскания такого числа k, при котором вычисление C _k, производимое с числом n, в точности совпадает с вычислением A( n, n) при любом n, и подстановки  p= q= k. Для того чтобы проделать это же в явном виде, отыщем машинное предписание  K(= C _k), действие которого на последовательность символов на ленте

… 00111110n11111000…

(где  nесть пятеричная запись числа n) в точности совпадает с действием алгоритма  Aна последовательность

… 00111110n111110n11111000…

при любом n. Таким образом, действие предписания  Kсводится к тому, чтобы взять число  n(записанное в пятеричном выражении) и однократно его скопировать, при этом два  n разделяются последовательностью 111110(та же последовательность начинает и завершает всю последовательность отметок на ленте). Следовательно, оно воздействует на получаемую в результате ленту точно так, как на эту же ленту воздействовал бы алгоритм A.