/
Теги: фундаментальные и общие проблемы математики основы математики математическая логика
ISBN: 5-03-003067-0
Текст
COMPUTABILITY
AND LOGIC
Third edition
GEORGE S. BOOLOS
Professor of Philosophy
Massachusetts Institute of Technology
RICHARD C. JEFFREY
Professor of Philosophy
Princeton University <
Л**-~т4*~А'
Ивтг VIII to им.
Пг IMwrtltr km frm/Ы
CAMBRIDGE UNIVERSITY PRESS
CAMBRIDGE
NEW YORK PORT CHESTER
MELBOURNE SYDNEY
Дж. Булос, Р. Джеффри
Вычислимость
и
логика
Перевод с английского
В.А.Душского и Е.Ю.Ногиной
под редакцией
С. Н. Артемова
Москва «Мир» 1994
ББК 22.12
Б90
УДК 510
Булос Дяс., Джеффри Р.
Б90 Вычислимость и логика. Пер. с англ. — М., Мир, 1994 —
396с, ил.
ISBN 5-03-003067-0
Книга известных американских математиков, являющаяся в настоя-
настоящее время одной из наиболее известных в США книг по математической
логике, выдержавшая там три издания A974, 1980, 1989 гг.). В ней со-
содержатся начала и некоторые дополнительные главы математической
логики, последовательно и строго излагаются классические теоремы о
неразрешимости логики предикатов и разрешимости некоторых ее фраг-
фрагментов, знаменитые теоремы Гёделя о полноте, нестандартные модели
и многое другое. Материал дополнен упражнениями.
Для всех, кто интересуется математической логикой, а также ин-
информатикой, философией и лингвистикой.
ББК 22.12
Издание осуществлено при финансовой поддержке
Российского фонда фундаментальных исследований
согласно проекту 94-01-21086
Редакция литературы по математическим наукам
ISBN 5-03-003067-0 (русск.)
ISBN 0-521-38923-2 (англ.)
© Cambridge University Press 1974,
1980, 1989
© перевод на русский язык,
Душский В. А., Ногина Е. Ю.,
1994
Предисловие редактора перевода
Эта книга написана профессором Массачусетского технологиче-
технологического института Джорджем Булосом и профессором Принстонского
университета Ричардом Джеффри на основе их многолетнего опыта
преподавания логики студентам и аспирантам разных специально-
специальностей и является в настоящее время одной из наиболее известных в
США книг по математической логике.
Она может рассматриваться как учебное пособие для старше-
старшекурсников и аспирантов (в этом качестве она широко используется
в американских университетах), хотя живой стиль изложения де-
делает ее весьма привлкательной для широкого круга читателей, ин-
интересующихся математической логикой, в том числе основаниями
математики, информатикой, лингвистикой, философской логикой
и т.д. Мы также адресуем эту книгу тем, кто решит самостоя-
самостоятельно изучить основы логики.
Книга содержит ряд важных разделов, которые, насколько нам
известно, не публиковались прежде в учебной литературе на рус-
русском языке и значительно выигрывает от наличия большого коли-
количества упражнений и задач.
v Первые 13 глав носят вводный характер, но даже в этом стан-»
дартном объеме того, что в американских университетах носит на-
¦ звание «baby logic», читатели обнаружат приятный сюрприз: про-
, стейшая модель вычислимости на абаке и доказательство ее экви-
эквивалентности вычислимости машинами Тьюринга. Вычисление на
а абаке, а в российском варианте это хорошо знакомые «счеты» —
.-.• древний способ сложения и умножения чисел; как показывается в
, книге, абак способен моделировать любую вычислимую функцию.
jj Читатель получает ясное представление о том, что Вычислимость
'1 не является искусственным изобретением 20-века, но столь же есте-
естественна, как Доказуемость и Истинность, которые вместе с Вычи-
Вычислимостью являются основными понятиями логики.
* Знаменитые теоремы Гёделя о неполноте и теорема Чёрча о не-
' разрешимости доказаны в гл. 14-16. Здесь авторы следуют совре-
современной манере изложения, которая состоит в доказательстве в об-
общем виде леммы о диагонализации, а затем применении этой леммы
к формуле для гёделевых номеров недоказуемых формул. Подобное
изложение отделяет прямую процедуру построения формулы до-
доказуемости от диагональной конструкции, тем самым изгоняя из
б Предисловие редактора перевода
доказательства теорем о неполноте мистический элемент. Теперь,
после доказательства неразрешимости арифметики с операциями
сложения и умножения, совершенно уместной выглядит теорема
Пресбургера о разрешимости арифметики сложения (гл. 21).
Теорема Тарского о неорпеделимости и связанные с ней вопросы
приводятся в гл. 15, 19 и 20. В частности, в гл. 20 доказан класси-
классический результат Аддисона о неопределимости самого класса опре-
определимых множеств. В гл. 17 и 29 изложен ряд теорем, имеющих от-
отношение к двум фундаментальным фактам о моделях арифметики:
существуют счетные модели арифметики первого порядка, отлич-
отличные от стандартной модели, — множества {0,1,2,...} с операциями
сложения и умножения, но стандартная модель — единственная, в
которой сложение и умножение являются вычислимыми функция-
функциями. Наконец, в гл. 26, 27 и 28 приводятся некоторые альтернатив-
альтернативные (негёделевые) способы построения независимых в арифметике
утверждений. Так, в гл. 26 доказывается теорема Рамсея и приво-
приводится основанный на ней пример Париса - Харрингтона истинного
математического утверждения, недоказуемого л формальной ариф-
арифметике Пеано. В гл. 27 дается понятие о модальной теории дока-
доказуемости. В рамках этого подхода гёделева. формула доказуемости
рассматривается как новый одноместный логический оператор, и
предлагается система аксиом для пропозициональной логики с опе-
оператором доказуемости. Эта логика дает описание широкого класса
независимых в формальной арифметике предложений, полученных
комбинацией булевых связок и оператора доказуемости. Наконец, в
гл. 28 приводятся теоремы о неполноте арифметики, полученные
Россером, Чейтином и Булосом.
Интерполяционная лемма Крейга (гл. 23) демонстрирует важ-
важное свойство релевантности классической логики: для каждой об-
общезначимой формулы А —> В найдется интерполянт С, т.е. формула,
которая содержит только нелогические символы, общие для А к В,
такая, что общезначимы А—*СиС—*В. В частности, импликация
А —> В, в которой Л и В не имеют общих нелогических символов,
общезначима только в вырожденных случаях, когда общезначи-
общезначима В или невыполнима А. В качестве приложений интерполяци-
интерполяционной леммы в гл. 24 приводятся классические теорема Робинсона
о непротиворечивости и теорема Бета об определимости.
Точная граница разрешимости фрагментов логики первого по-
порядка, определяемых размерностью нелогических символов, уста-
устанавливается в гл. 22 и 25. Показано, что логика, содержащая лишь
Предисловие редактора перевода 7
одноместные предикаты, разрешима, но что уже логика с одним
двуместным предикатом неразрешима.
К русскому изданию авторы добавили в гл. 10 раздел с доказа-
доказательством неразрешимости логики первого порядка по Гёделю.
Редактор перевода благодарит авторов этой книги Дж. Булоса
и Р. Джеффри, а также спонсора русского издания:
; SCHOOL OF HUMANITIES AND SOCIAL SCIENCE
MASSACHUSETTS INSTITUTE OF TECHNOLOGY
* CAMBRIDGE, MASSACHUSETTS 02139
USA
Именно их поддержка проекта перевода книги была решающей.
Редактор выражает искреннюю признательность переводчикам
В. А. Душскому (предисловие авторов и гл. 1-13) и Ё. Ю. Ноги-
Ногиной (гл. 14-29), ведущему редактору издательства Г. М. Цукерман.
немало способствовавшей улучшению текста перевода, М. Пентусу,
составившему «оригинал-макет» данного издания.
С. Артемов
Логическая зависимость глав
(| означает «предполагает знакомство с»)
Предисловие
Посвящается Ребекке и Эдит
Вычислимость и логика адресована тем изучающим философию
или чистую или прикладную математику, кто уже овладел мате-
материалом, содержащимся обычно во вводном курсе логики, и хотел
бы углубить свое знакомство с предметом. Основная задача кни-
книги — изложить важнейшие теоретические результаты о логике, а
также представить некоторые другие металогические результаты,
доказательства которых трудно почерпнуть из других источников.
Мы старались сделать текст настолько удобочитаемым, насколь-
насколько это совместимо с изложением полных доказательств, приводить
наиболее элегантные из известных нам доказательств, употреблять
стандартные обозначения и «сгладить углы» (в той мере, в какой
это осуществимо технически).
Вот краткое содержание книги. Вначале мы вводим понятие
счетности (перечислимости, нумеруемости) и устанавливаем суще-
существование несчетных множеств. Затем определяется понятие вычи-
вычислимости посредством машин Тьюринга и доказывается, что про-
проблема их остановки неразрешима. Мы вводим еще два понятия
вычислимости и доказываем их эквивалентность вычислимости по
Тьюрингу. Неразрешимость (элементарной) логики первого поряд-
порядка выводится непосредственно из неразрешимости проблемы оста-
остановки, без использования «арифметизации». Затем устанавливают-
устанавливаются корректность и полнота некоторой системы логического вывода.
Теорема Лёвенгейма-Сколема в редакции «всякая интерпретация
обладает элементарно эквивалентной подинтерпретацией со счет-
счетной областью» устанавливается при доказательстве корректности и
полноты. Затем доказывается, что все рекурсивные функции пред-
ставимы в арифметике Робинсона Q, вслед за чем мы выводим тео-
теорему Чёрча о неразрешимости логики первого порядка (повторно),
теорему Тарского о неопределимости и первую теорему Гёделя о
неполноте в форме «не существует полного непротиворечивого ак-
аксиоматизируемого расширения теории Q». Затем мы доказываем
различные варианты второй теоремы Гёделя о неполноте и тео-
теорему Лёба, обсуждаем существование и природу нестандартных
моделей арифметики и выявляем (резкие) различия между логи-
10
Предисловие
ками первого и второго порядков. Мы показываем, что, в про-
противоположность теореме Тарского о неопределимости-, арифмети-
арифметическая истинность определима в арифметике второго порядка, а
некоторые «аппроксимации» арифметической истинности могут
быть определены и в арифметике первого порядка. Затем дока-
доказывается теорема Аддисона, гласящая, что класс множеств (на-
(натуральных чисел), определимых в арифметике, сам в арифметике
не определим. Затем мы приводим теорему Пресбургера о том, что
арифметика становится разрешимой, если убрать из нее умножение.
Доказывается интерполяционная лемма Крейга, из которой выво-
выводятся теорема Робинсона о непротиворечивости и теорема Бета об
определимости. Наконец, мы устанавливаем разрешимость мона-
дической логики с равенством и неразрешимость логики без равен-
равенства, содержащей единственный двуместный предикатный символ.
Р. Джеффри является главным автором гл. 1-9, Дж. Булос —
гл. 13-25. Главы 10, И и 12 написаны совместно.
Мы хотим поблагодарить Саймона Кочена и Саула Крипке за
два усовершенствования, существенно улучшивших гл. 14. Кочен
предложил воспользоваться тем, что рекурсивные функции — это
функции, получающиеся с помощью композиции и минимизации из
проектирующих функций, сложения, умножения и характеристиче-
характеристической функции отношения равенства; доказательство представимо-
представимости всех рекурсивных функций в Q существенно при этом упроща-
упрощается. Идея отказа от китайской теоремы об остатках за счет исполь-
использования конкатенации над переменным простым основанием для
построения некоторой /^-функции принадлежит Крипке. Мы также
признательны П. Бенасеррафу, Б. Дребену, X. Филду, К. Глимору,
У. Голдфарбу, Д. Люису, П. Меллема, X. Патнаму, У. В. О. Куайну,
Т. М. Скенлону, Дж. Томсону и П. Тови за исправления, замечания
и предложения. Наконец, мы обязаны книгам Чёрча, Эндертона,
Клини, Крайзеля, Кривина, Шенфилда, Тарского, Мостовского и
Робинсона.
Август 1973 г.
Джордж Булос
Ричард Джеффри
Предисловие к третьему изданию
Глава 28 о неразрешимых предложениях и гл. 29 о несущество-
несуществовании нестандартных рекурсивных моделей теории Z являются в
настоящем, третьем издании совсем новыми. Главы 26 и 27 су-
существенно пересмотрены, а кроме того, гл. 8, 18 и 19 пополнены
новыми упражнениями.
Р. Джеффри хочет подчеркнуть, что Дж. Булос несет ответ-
ответственность за все изменения по сравнению с первым изданием.
Декабрь 1988 г.
Джордж Булос
Ричард Джеффри
V
Счетность
Сметным называют всякое множество, элементы которого мо-
могут быть занумерованы, т.е. расположены в виде единого списка, в
¦ котором какой-то элемент стоит первым, какой-то — вторым и т.д.,
так что всякий элемент данного множества рано или поздно встре-
встречается в этом списке1. Примеры: множество Р натуральных чисел
нумеруется списком
1,2,3,4,...,
а множество Е четных чисел — списком
2,4,6,8,....
Разумеется, в этих списках фигурируют не сами натуральные чи-
числа, а лишь их имена. При перечислении элементов какого-либо
множества (скажем, сенаторов США) вы оперируете с именами
этих элементов, а не с объектами, ими поименованными. (Вам не
нужно выстраивать в очередь сенаторов; вместо этого вы распола-
располагаете в виде списка их имена — например, в алфавитном порядке.)
Снисходительно мы признаем счетным и пустое множество 0,
не содержащее ни одного элемента. (Существует единственное пу-
пустое множество. Терминология здесь не совсем удачна: она подтал-
подталкивает к сравнению пустых множеств с пустыми контейнерами.
Лучше, однако, сравнивать множества с содержимым контейнеров,
после чего остается заметить, что пустые контейнеры имеют одно
и то же, пустое, содержимое.)
Список, нумерующий то или иное множество, может быть конеч-
конечным или бесконечным. Бесконечное множество, являющееся счет-
счетным, называют счетно бесконечным или же просто счетным. По-
Постараемся уточнить, какие объекты рассматриваются нами в каче-
качестве бесконечных списков, а какие — нет. Например, натуральные
Строго говоря, здесь определено, конечно, непустое (если только не допус-
допускать пустые списки) не более чем счетное множество. Мы, однако, как это де-
делается порою в отечественной литературе, предпочитаем использовать вместо
этого краткий термин «счетный», полагая, что читатель всегда может прояс-
прояснить для себя ситуацию из контекста. — Прим. перев.
1. Счетность
13
числа можно расположить в виде единого бесконечного списка ука-
указанным выше способом, в то время как
1, 3, 5, 7,..., 2, 4, 6, 8,...
не рассматривается нами как список того же множества. Здесь вна-
вначале перечислены все нечетные числа и лишь затем — четные. Это
не разрешается. В допустимом списке каждый элемент должен (ра-
(рано или поздно) появляться на n-м месте при некотором конечном п.
Но в приведенном выше недопустимом расположении ни одно из
четных чисел не удовлетворяет этому условию. Они, так сказать,
появляются на местах с номерами оо + 1, оо + 2 и т.д.
Чтобы окончательно прояснить этот момент, мы можем опре-
определить нумерацию произвольного множества не как список, а как
соответствие, при котором каждый элемент этого множества со-
сопоставляется одному из натуральных чисел 1, 2, 3,.... В дей-
действительности всякий список и есть такое соответствие. Элемент,
стоящий на первом месте в списке, ставится в соответствие, таким
образом, числу 1, элемент, стоящий на втором месте, — числу 2, и
вообще, элемент, занимающий n-е место, ставится в соответствие
числу п.
При нумерации множества путем выписывания его элементов
вполне допускается, чтобы какой-либо элемент множества появил-
появился в этом списке более одного раза. Требуется лишь, чтобы каждый
элемент появился хотя бы раз. Не имеет значения, если в списке
содержатся повторения; мы требуем лишь, чтобы он был полным.
Действительно, всякий список с повторениями можно путем проре-
прореживания превратить в бесповторный. (Каждый из последовательно
появляющихся элементов сравнивайте с конечным множеством ра-
ранее появившихся в нем элементов. Вычеркните этот элемент, если
он уже появлялся ранее.)
Говоря математическим языком, всякий бесконечный список
определяет функцию (назовем ее /), аргумент которой пробегает
натуральные числа, а значениями служат элементы перечисляе-
перечисляемого множества. Значение функции / для значения аргумента п
обозначается через /(п). Это значение есть просто объект, стоя-
стоящий в нашем списке на n-м месте. Таким образом, список
2, 4, 6, 8,...,
14
1. Счетностъ
перечисляющий множество Е четных чисел, определяет функцию /,
для которой
= 2, /B) = 4,
= 6, /D) = 8,....
Обратно, функция / определяет (с точностью до обозначений) этот
список. (Тот же самый список при использовании двоичной запи-
записи имел бы вид 10, 100, ПО, 1000,—) Итак, мы могли бы сначала
задать функцию /, объявив, что /(п) = 2п для всякого натурально-
натурального п, а затем определить соответствующий ей список, сказав, что
п-е место в нем занимает десятичная запись числа /(п), т.е. чи-
числа 2п.
Теперь мы можем говорить, что множества перечисляются
функциями в той же мере, как и списками. Например, вме-
вместо того чтобы перечислять множество нечетных чисел списком
1, 3, 5, 7,..., мы можем занумеровать его с помощью функции,
ставящей в соответствие натуральному п значение 2п— 1, а перечи-
перечисление множества Р всех натуральных чисел списком 1, 2, 3, 4,...
заменить его нумерацией с помощью функции, ставящей в соответ-
соответствие натуральному п в качестве значения то же самое п. (Это —
тождественная функция. Если обозначить ее i, то i(n) = n для
всякого натурального п.)
Если какая-либо функция нумерует некоторое непустое множе-
множество, то эту же задачу решает и некоторая другая функция, а в
действительности бесконечно много других функций2. Таким обра-
образом, множество всех натуральных чисел перечисляется не только
функцией », но и функцией (назовем ее </), определяемой списком
2, 1, 4, 3, б, 5,... .
Этот список получен из списка 1, 2, 3, 4, 5, 6,... попарной пе-
перестановкой элементов: 1 с 2, 3 с 4, 5 с 6 и т.д. Этим списком за-
задается несколько странная, но вполне приемлемая нумерация мно-
множества Р: всякое натуральное число рано или поздно появляется в
нем. Соответствующая функция g определяется следующим обра-
образом:
i+l, если п нечетно,
1—1, если п четно.
9(п) =
2 Это утверждение верно, если в данном множестве содержится более од-
одного элемента или если допускать к рассмотрению и не всюду определенные
функции. — Прим. перес.
1. Счетность
15
Это определение не так изящно, как определения f(n) = 2п и
j(n) = г» функций / и I, но оно выполняет требуемое — каждо-
каждому натуральному п ставит в соответствие один и только один
элемент множества Р. И главное, так определенная функция g дей-
действительно перечисляет множество Р: для всякого элемента m из Р
существует такое натуральное п, что д(п) = т.
Мы уже отмечали, что вполне допустимы списки, перечи-
перечисляющие данное множество с повторениями, так как при жела-
желании мы всегда можем путем прореживания эти повторения уда-
удалить. Допустима и ситуация, когда в списке на некоторых ме-
местах отсутствуют элементы, поскольку в этом случае можно, по-
последовательно продвигаясь по списку, «стянуть» эти дыры. Та-
Таким образом, следующий содержащий пробелы список задает впол-
вполне удовлетворительную нумерацию множества натуральных чи-
чисел:
1, —, 2, —, 3, —, 4, —, 5, —, б, —,... .
Соответствующая функция (назовем ее Л) приписывает значе-
значение первой, третьей, пятой,... позициям списка, но не припи-
приписывает никаких значений позициям, соответствующим пробелам
списка (второй, четвертой, шестой,...). Таким образом, имеем
ЛA) = 1, а ЛB) не равно ничему, так как функция Л не опре-
определена для значения аргумента 2; ЛC) = 2, но ЛD) не опре-
определено; ЛE) = 3, но /»F) не определено. Итак, Л — частич-
частичная {не всюду определенная) функция на множестве натураль-
натуральных чисел, поскольку она определена лишь для нечетных зна-
значений аргумента, но не для всех его возможных значений. Мы
могли бы следующим явным образом определить эту функ-
функцию Л:
h{n) — (n + 1)/2, если п нечетно.
Или, чтобы не возникло подозрения, будто мы просто забыли ука-
указать, какие значения приписывает функция Л четным числам, мож-
можно было бы сформулировать это определение следующим обра-
образом:
(п + 1)/2, если п нечетно,
не определено в противном случае.
Таким образом, частичная функция Л задает несколько странную,
но вполне допустимую нумерацию множества Р натуральных чи-
чисел.
16
1. Счетность
Было бы нелепо использовать для перечисления множества Р
функцию h вместо гораздо более подходящей функции f; однако дру-
другие множества более естественно нумеруются именно частичными
функциями. Например, множество Е четных чисел удобно перечи-
перечислить с помощью частичной функции (назовем ее j), совпадающей
с функцией i для четных значений аргумента и не определенной для
нечетных значений:
¦( \ — ) п> если п четно,
[_ не определено в противном случае.
Соответствующий ей содержащий пробелы список имеет (в деся-
десятичной записи) вид
-, 2, -, 4, -, 6, -, 8,... .
Конечно, и функция/, определяемая равенством '.'"'.
для всех натуральных п, задает в равной степени допустимую нуме-
нумерацию множества Е, соответствующую сплошному, без пробелов,
списку
2,4,6,8
Произвольное множество 5", состоящее из натуральных чисел,
очень легко перечисляется подходящей частичной функцией, опре-
определяемой следующим образом:
v ' [не
если п 6 S,
не определено в противном случае.
Так, например, множество {1,2,5}, состоящее из чисел 1, 2 и 5,
перечисляется частичной функцией к, определяемой соотношением
i / ч _ Г п, если п = 1, или п = 2, или п = 5,
[ не определено в противном случае.
В следующей главе мы увидим, что, хотя всякое множество,
состоящее из натуральных чисел, счетно3, существуют тем не
Это утверждение было, очевидно, доказано в предпоследнем абзаце, где
демонстрировалась возможность перечисления произвольного такого множе-
множества 5 подходящей частичной функцией з. — Прим. перее.
1. Счетность
17
менее несчетные множества (естественно, не содержащиеся в мно-
множестве Р). Чтобы убедиться в счетности множества А, нужно до-
доказать, что существует функция, область определения которой со-
состоит из натуральных чисел, а всякое значение является элементом
множества А, причем всякий элемент множества А является одним
из ее значений: для всякого элемента а множества А существует
хотя бы одно натуральное п, которому функция приписывает а в
качестве ее значения. Отметим, что в этом определении нет ни сло-
слова о том, что А должно состоять из натуральных чисел. Напротив,
А может оказаться множеством людей (например, сенаторов США);
оно может быть множеством строчек символов (например, мно-
множеством всех грамматически правильных фраз английского язы-
языка, причем пробел между соседними словами мы считаем одним
из символов). Элементы множества А сами могут оказаться мно-
множествами, как, например, в случае А = {Р,Е,0}. Здесь А есть
множество из трех элементов, каждый из которых сам является
множеством. Один из его элементов есть бесконечное множество Р
всех натуральных чисел, другим элементом служит бесконечное же
множество Е всех четных чисел, третий элемент — это пустое мно-
множество 0. Множество А, очевидно, счетно, что устанавливается
выписыванием его конечного списка
Р, Е, 0.
Каждую позицию в этом списке занимает некоторый элемент мно-
множества А, причем каждый элемент из А рано или поздно упоми-
упоминается в этом списке. Этот список задает некоторую функцию —
назовем ее /, — определяемую следующими тремя равенствами:
E, Д3) = 0.
Точнее говоря, / есть частичная функция на множестве натураль-
натуральных чисел, не определенная для значений аргумента, больших 3.
Мораль: функция на множестве натуральных чисел, частичная или
всюду определенная, может принимать значения в совершенно про-
произвольном множестве. Все значения ее аргумента обязаны быть
натуральными числами, но значения самой функции могут нату-
натуральными числами и не быть.
Множество всех конечных слов, составленных из букв (латин-
(латинского) алфавита, доставляет пример счетно бесконечного множе-
множества, состоящего не из натуральных чисел. Счетность этого мно-
множества доказывается возможностью расположить его элементы в
2—249
18
1. Счетность
виде единого списка, который мы опишем, не выписывая в явном
виде. Первые 26 мест в списке занимают 26 букв данного алфавита
в их обычном порядке. Следующие 676 (= 262) позиций занимают
двухбуквенные слова в словарном (лексикографическом) порядке.
Следующие 17576 (= 263) позиций заняты трехбуквенными слова-
словами, опять же в словарном порядке. И так далее, без конца. Исходя из
этого описания, с помощью карандаша, бумаги и терпения вы смо-
сможете определить, какое место в списке занимает любое интересую-
интересующее вас слово. Таким образом, мы определили в действительности
некоторую функцию на множестве натуральных чисел, перечисля-
перечисляющую рассматриваемое множество. Это определение не имеет вида
математических равенств, но, несмотря на это, оно вполне при-
пригодно: оно решает поставленную задачу, состоящую в том, чтобы
всякому натуральному числу, рассматриваемому в качестве значе-
значения аргумента, ставить в соответствие некоторый элемент нашего
множества в качестве значения функции. И поскольку это опреде-
определение совершенно ясно и недвусмысленно, не имеет значения, что
оно изложено на разговорном языке, а не на языке математических
символов.
Поскольку слова, элементы рассматриваемого множества, могут
быть зафиксированы в письменной форме, правомерно говорить,
что на этот раз в список заносятся сами эти элементы. Можно,
однако, говорить об элементах списка как об именах этих слов,
чтобы по-прежнему считать, что при перечислении множества в
список попадают именно имена его элементов.
В заключение приведем в порядок нашу терминологию.
Функцией будем называть всякое правило, ставящее в соот-
соответствие значения функции значениям ее аргумента. Множество
всех значений аргумента, которым ставятся в соответствие зна-
значения функции, называют областью определения этой функции.
Множество всех значений функции, которые ставятся в соответ-
соответствие значениям ее аргумента, называют множеством значений
функции. В случае функций, значениями аргумента которых слу-
служат натуральные числа, мы различаем всюду определенные и ча-
частичные (не всюду определенные) функции. Всюду определенная
функция на множестве натуральных чисел характеризуется тем,
что ее область определения есть все множество Р натуральных
чисел. Частичная функция на множестве натуральных чисел есть
функция, областью определения которой служит какое-либо под-
подмножество всего множества Р. Начиная с этого момента, говоря
1. Счетность
19
о функции на множестве натуральных чисел, мы будем считать,
что речь может идти как о всюду определенной, так и о частич-
частичной функции. Это отступление от привычной терминологии, когда
«функция» (на множестве натуральных чисел) понимается как всю-
всюду определенная функция. Мы далее будем рассматривать как пол-
полноценную частичную функцию на множестве натуральных чисел
так называемую нигде не определенную функцию е, область опре-
определения которой — пустое множество. Эта функция не определена
ни для одного значения аргумента! Множество называется далее
счетным, если оно есть множество значений некоторой функции
на множестве натуральных чисел. Пустое множество счетно, по-
потому что оно является множеством значений функции е.
Пример. Множество положительных рациональных чисел
счетно.
Число называется положительным рациональным, если оно
представимо в виде отношения натуральных чисел, т.е. в виде т/п,
где тип — натуральные числа. Прежде чем перечислять рацио-
рациональные числа, расположим их в виде прямоугольного массива, как
в табл. 1-1(а).
Таблица 1-1
(а)
1
т
1
2
1
3
1
4
1
5
2
1
2
2
2
3
2
4
2
5
3
1
3
2
3
3
3
4
3
5
4
Т
4
2
4
3
4
4
4
5
5
Т
5
2
5
3
5
4
5
5
(Ь)
1 2 5 10 17
4 3 6 И 18
9 8 7 12 19
16 15 14 13 20
25 24 23 22 21
Всякое положительное рациональное число представлено в
каком-либо месте этого массива. Так, число т/п находится на пе-
пересечении гп-го столбца и n-й строки. На самом деле всякое та-
такое число представлено в нашей таблице бесконечно много раз, по-
поскольку т/п, 2т/2п, Zm/in,... представляют одно и то же число.
20
1. Счетность
В частности, число 1 занимает все позиции на главной диагонали в
табл. 1 - 1(а): пересечение первого столбца и первой строки, второго
столбца и второй строки и т.д.
Чтобы убедиться, что положительные рациональные числа
образуют счетное множество, мы должны выписать элементы
табл. 1-1(а) в виде единого списка. Сделать это можно различ-
различными способами, например так, как это показано в табл. 1-1(Ь),
где номер в каждой клеточке таблицы указывает положение стоя-
стоящего в ней рационального числа в создаваемом списке рассматрива-
рассматриваемого множества. Тогда список, в котором каждое положительное
рациональное число фигурирует бесконечно много раз, оказывается
следующим:
12 2 13
I' Г 2' 2' Т'"" "
Два массива, приведенные в табл. 1-1, дают в совокупности
вполне удовлетворительное определение функции (назовем ее г) на
множестве натуральных чисел, перечисляющей все положительные
рациональные числа. Имеем
или, после сокращения,
\
гA) = 1, гB) = 2, гC) = 1, гD) = ±, гE) = 3,
Совершенно ясно, как функция г определяется этими двумя мас-
массивами: если дано произвольное натуральное п, то для вычисле-
вычисления г(п) нужно просто строить оба массива до того момента, когда
во втором из них появится число п. Значение г(п) находится тогда в
ячейке первого массива, имеющей те же «координаты». Занятно —
хотя и вовсе не обязательно — дать более математикообразное опре-
определение функции г. Если вы хотите попытаться сделать это, то вот
вам указание: всякое натуральное п лежит в некотором интервале
между двумя соседними полными квадратами, т.е. для всякого п
существует в точности одно га, для которого (га— IJ < п<га2.
Введем обозначение sq для функции, вычисляющей по п это значе-
значение га. Задача теперь состоит в том, чтобы нужным образом заме-
заменить вопросительные знаки в следующем определении, содержащем
значение п и функцию sq:
¦)/?, если ?,
) в противном случае.
1. Счетность
21
Но если задачи такого рода вас угнетают, то и не мучайтесь с нею.
Если же вы попытаетесь ее решить, то проверить свой ответ вы
сможете, взглянув ниже на решение упр. 1.1.
Упражнения. (Решения приведены после списка упражнений.)
1.1. Сформулируйте определение функции г в указанной выше
форме, где sq(n) — наименьшее натуральное число, квадрат кото-
которого больше или равен п. Указание. Сначала выпишите несколько
первых элементов m-й строки и га-го столбца табл. ] -1.
1.2. Докажите счетность множества всех целых чисел, перечи-
перечислив их с помощью единого бесконечного списка, обладающего, од-
однако, началом; запишите также математикообразное определение
функции, соответствующей вашему списку.
1.3. Докажите счетность множества всех рациональных чисел
(положительных, отрицательных и нуля), перечислив их с помо-
помощью единого бесконечного списка (обладающего опять-таки на-
начальным элементом).
1.4. Докажите счетность множества всех конечных последова-
последовательностей из плюсов и минусов, описав единый список, перечисля-
перечисляющий это множество.
1.5. Покажите теперь, что счетно и множество всех конечных
множеств натуральных чисел, описав способ, с помощью которо-
которого конечные последовательности плюсов и минусов могут быть ис-
использованы как имена для конечных множеств натуральных чисел.
1.6. Пусть D — множество множеств натуральных чисел, опре-
определяемое следующим образом: множество натуральных чисел при-
принадлежит множеству D тогда и только тогда, когда оно определимо
с помощью конечного количества слов русского языка. Таким обра-
образом, следующие множества принадлежат множеству D, поскольку
каждое из них определяется указанным образом:
Е: множество всех четных натуральных чисел
...; E СЛОВ),
, 0 : множество, не содержащее ни одного элемента
; . F слов),
{1,2} : множество, единственными элементами которо-
. го являются числа один и два (9 слов),
{1,..., 999} : множество всех натуральных чисел, меньших
чем тысяча G слов)
и т. д. Докажите; что множество D счетно бесконечно.
22
Решения
1. Счетность
1.1. Вспоминая, что га = sq(n), замечаем, что т-е строка и стол-
столбец имеют вид
(а)
eq(n)/l
sq(n)/2
sq(n)/3
l/sq(n) 2/sq(n) 3/sq(n) ... sq(n)/sq(n)...
(b)
(sq(n) - IJ + 1
(sq(n)-lJ+2
(sq(n)-lJ+3
(sq(n)J-0 (sq(n)J-l (sq(n)J - 2 ... (sq(n) - IJ + ra.
Искомое определение принимает тогда вид
sq(n)
r(u) =
n-(sq(n)-lJ
(sq(n)J + 1 - n
sq(n)
, если n < (sq(n) — IJ + sq(n),
в противном случае.
Это, конечно, очень мило, но ничуть не более прозрачно, чем опре-
определение функции г с помощью массивов из табл. 1-1.
1.2. Простейший список таков: 0, 1, —1, 2, —2, 3, —3, Тогда
если соответствующую функцию назвать /, то /A) = 0, /B) = 1,
/C) = — 1, /D) = 2 и т.д. Приведем математикообразное определе-
определение функции /:
п-1
если п нечетно,
если п четно.
1.3. Вы уже знаете, как с помощью единого бесконечного списка
перечислить положительные рациональные числа. Поместим перед
. Счетность
23
этим списком число 0, а еще левее в обратной последовательности
запишем те же положительные рациональные числа, но со знаком
минус перед каждым. Тогда мы получим
..., _з, -I, -1, -2, -1, 0, 1, 2, 1, ^, 3,... .
а ¦
Ф заключение, воспользовавшись приемом из упр. 1.2, превратим
в настоящий список:
О, 1, -1, 2, -2, 1, -1, i, -i, 3, -3,... .
1.4. Вот их перечисление:
Опишем этот список: сначала выписываются последовательности
длины 1, затем последовательности длины 2, за ними последова-
последовательности длины 3 и т.д.; внутри каждой из этих групп последова-
последовательности располагаются в словарном порядке, причем + считается
предшествующим знаку — в соответствующем «алфавите». (Таким
образом, следующие шесть позиций занимают последовательности
1.5. Будем интерпретировать конечную последовательность
(плюсов и минусов) как имя множества, которому число п при-
принадлежит, если в последовательности имеется n-й символ и этот
символ — плюс, и не принадлежит, если в последовательности
имеется менее п символов или n-й символ имеется, но является
минусом. Теперь каждое конечное множество натуральных чисел
получило имя. На самом деле оно получило даже бесконечно мно-
много имен; так, например, пустое множество 0 имеет имена —, —,
и т.д., а множество {1,2,5} имеет имена -Н К -Н 1—,
+Н 1 и т.д.
1.6. Конечно же, множество D бесконечно, поскольку среди его
членов содержатся все множества из следующей бесконечной их со-
совокупности:
{1} : множество, единственным элементом которого
является число один,
{2} : множество, единственным элементом которого
является число два,
24
1. Сметность
Поскольку в русском языке имеются наименования для всех нату-
натуральных чисел, то это подмножество множества D бесконечно, а
потому бесконечно и само D. Счетность же множества D вытека-
вытекает из того факта, что всякое определение множества натуральных
чисел на русском языке представляет собой конечную последова-
последовательность символов, каждый из которых является одной из 33 букв
алфавита (если пренебречь заглавными буквами и пунктуацией)
либо пробелом (отделяющим соседние слова), трактуемым нами
как 34-я буква алфавита. (Если вам не хочется отказываться от
заглавных букв и знаков препинания, то следует добавить эти сим-
символы к описанному алфавиту. При этом получится по-прежнему
конечный, хотя и больший алфавит.) Теперь можно занумеровать
конечные последовательности символов в полученном расширенном
алфавите: сначала перечисляются последовательности длины 1, за-
затем последовательности длины 2 и т.д.; в каждой из этих групп
последовательности располагаются в словарном порядке (причем
порядок символов в нашем расширенном алфавите устанавлива-
устанавливается произвольным образом). Большинство позиций в этом спис-
списке заполнено тарабарщиной, а также текстами, имеющими смысл,
но вовсе не определений множеств натуральных чисел. Удалим все
такие тексты. В результате останется список с пробелами, перечи-
перечисляющий все русскоязычные определения множеств натуральных
чисел.
Диагонализация
Не все множества счетны: некоторые слишком велики для этого.
Примером служит множество всех множеств натуральных чисел.
Это множество (обозначим его Р*) содержит в качестве элементов
любое конечное, равно как и любое бесконечное, множество нату-
натуральных чисел: пустое множество 0, множество Р всех натураль-
натуральных чисел, а также любое множество, промежуточное между этими
двумя крайностями.
Чтобы доказать (следуя Георгу Кантору) несчетность множе-
множества Р*, мы излагаем некий метод, применимый к произвольно-
произвольному списку L множеств натуральных чисел и позволяющий постро-
построить некоторое множество D(L) натуральных чисел, в этом списке
не фигурирующее. Если вы попытаетесь устранить дефект путем
включения множества D(L) в данный список в качестве нового
первого элемента, то тот же метод, примененный к обогащенно-
обогащенному списку V, породит новое множество D(L'), не содержащееся в
обогащенном списке!
Вот этот метод. Располагая произвольным бесконечным спис-
списком
Si'i S2, S3, ...
множеств натуральных чисел, мы следующим образом определяем
множество D(L):
мы считаем, что произвольное натуральное число п вхо-
входит в множество D(L) тогда и только тогда, когда п не (*)
содержится в Sn.
Как явствует из определения множества D(L), его построение за-
зависит от строения списка L, так что различные списки L поро-
порождают, вообще говоря, различные множества D{L) 1. Должно быть
ясно, что описание (*) действительно определяет некоторое множе-
множество D(L), поскольку для любого натурального числа п мы можем
1 Подчеркнем, что различные множества D(L) могут появиться, даже если
за исходный «материал» берутся различные списки L одного и того же мно-
множества. — Прим. перев.
26
2. Диагонализация
выяснить, принадлежит ли оно множеству D(L), если только нам
известно, содержится ли оно в n-м множестве списка L. Так, на-
например, если случится, что множество 5з есть множество Е всех
четных чисел, то число 3 не входит в 5з, а потому входит в D(L).
Чтобы убедиться в том, что определяемое указанным методом
множество D(L) никогда не содержится в исходном списке L, вос-
воспользуемся рассуждениями reductio ad absurdum: предположим, что
множество D(L) встречается где-то в списке L, скажем, входит в
него под номером т, и выведем отсюда противоречие, доказав тем
самым, что сделанное предположение ложно. Итак, сделаем пред-
предположение, что
Sm = ?>(L)
для некоторого натурального т. (Например, если в роли такого т
оказалось бы 127, то наше предположение означало бы, что D(L) и
5*127 — имена одного и того же множества, т.е. что всякое натураль-
натуральное число принадлежит множеству D(L) в точности тогда, когда
оно принадлежит 127-му множеству из списка L.) Чтобы вывести
из нашего предположения противоречие, применим определение (*)
к этому натуральному числу т: при п = m определение (*) говорит
нам, что
m входит в D(L) тогда и только тогда, когда т не входит в Sm.
Из сделанного предположения теперь вытекает противоречие: если
Sm и D(L) — одно и то же множество, то получается, что
m входит bD(L) тогда и только тогда, когда га не входит bD(L).
Поскольку мы пришли к явному противоречию, сделанное нами
предположение должно быть ложным. Следовательно, ни для како-
какого натурального т невозможно Sm = D(L). Иными словами, мно-
множество D(L) не содержится в списке L.
Таким образом, предложенный метод работает. Будучи приме-
применен к какому-либо списку множеств натуральных чисел, он по-
порождает новое множество натуральных чисел, не содержащееся в
данном списке. Поэтому никакой список не может перечислить все
множества натуральных чисел: множество Р* всех таких множеств
несчетно.
Рассматриваемый метод («диагонализации») настолько важен,
что было бы полезно взглянуть на него с несколько иной точки
2. Диагонализация
27
зрения, позволяющей придать элементам списка L более наглядную
форму. Будем теперь представлять множества Si, S2, • • • с помощью
функций »i, «2,..., определенных на множестве натуральных чисел
и принимающих значения 0 и 1. Связь между множеством Sn и
соответствующей функцией sn проста: для всякого натурального р
полагаем
1, если р входит в Sn,
О, если р не входит в Sn-
¦{¦
Тогда список L можно рассматривать как бесконечный прямоуголь-
прямоугольный массив из нулей и единиц, приведенный в табл. 2-1.
Таблица 2-1
«2
S3
«4
1
«2A)
«зA)
«4A)
2
«2B)
«зB)
«4B)-
3
«2C)
«зC)
«4C)
4
«$) :::
*зD) .'.'.
«4D) ...
': В этом массиве n-я строка представляет функцию sn, а потому
: множество Sn: строка
I: *пA) «пB) «„C) в„D) ...
есть последовательность нулей и единиц, в которой р-й элемент,
sn{p), равен 1 или 0 в зависимости от того, входит или не входит
число р в множество Sn- Элементы, стоящие на диагонали этого
массива (от верхнего слева до нижнего справа), также образуют
последовательность нулей и единиц:
«2B) *3C) «4D) ....
Эта последовательность нулей и единиц (диагональная последова-
последовательность) определяет множество натуральных чисел (диагональ-
(диагональное множество), которое вполне может содержаться среди пере-
перечисленных в списке L. Иными словами, вполне может существовать
такое натуральное число d, что множество S<j совпадает с нашим
28
2. Диагонализация
диагональным множеством. В этом случае последовательность ну-
нулей и единиц в d-тл строке табл. 2-1 оказалась бы совпадающей С
диагональной последовательностью: <|*'
*<*(!) = siQ). sdB) = s2B), «,C) = *зC), ... .
Итак, диагональное множество может содержаться или не содер-
содержаться в списке L в зависимости от конкретного устройства этого
списка. Нам же требуется множество, заведомо не входящее в L, как
бы ни был устроен список L. Оказывается, до такого множества нам
рукой подать: им будет так называемое антидиагональное множе-
множество, состоящее в точности из тех натуральных чисел, которые не
входят в диагональное множество. Соответствующая ему антидиа-
гональная последовательность получается из диагональной путем
замены в той нулей на единицы, а единиц — на нули. Это пре-
преобразование можно осуществить с помощью вычитания элементов
диагональной последовательности из единицы, т.е. антидиагональ-
антидиагональную последовательность можно записать в виде
1 - si(l), 1 - s2B), I - s3C), 1 - s4D), ....
Эта последовательность заведомо не может появиться в качестве
строки в табл. 2-1, так как, если бы такое произошло — окажись
она, например, m-й строкой, — мы имели бы
B) = l-
sm(m) = l-sm(m), ....
Ho m-e из этих равенств невозможно. (Доказательство. Величи-
Величина sm(m) должна быть нулем или единицей. Если она — нуль, то
m-e равенство утверждает, что 0=1. Если же она — единица, то
равенство говорит, что 1 = 0.) Значит, антидиагональная последо-
последовательность отличается от любой строки нашего массива, а по-
потому антидиагональное множество отлично от любого множества
из списка L. В этом нет ничего нового, поскольку антидиагональ-
антидиагональное множество — это просто множество D(L). По существу мы с
помощью табл. 2-1 повторили наше доказательство того факта,
что D(L) не может содержаться в списке L.
Конечно, менее ясным выглядит утверждение, что все элемен-
элементы некоторого бесконечного множества «можно расположить» в ви-
виде единого бесконечного списка. Но в чьих это силах? Разумеется,
это не по силам человеку, так как ни у кого не хватит для это-
этого ни времени, ни бумаги. Те же ограничения имеют место и для
2. Диагонализация
29
машин. На самом деле назвать множество счетным — это просто
сказать, что оно есть множество значений некоторой функции на
множестве натуральных чисел. Таким образом, например, множе-
множество Е четных натуральных чисел счетно, потому что существуют
функции на множестве натуральных чисел, для которых Е являет-
является множеством значений, — например, всюду определенная функ-
функция /(п) = 2п. Всякую такую функцию можно представлять себе
как программу, следуя которой некий перечислитель со сверхчело-
сверхчеловеческими возможностями мог бы расположить элементы данного
множества в виде единого списка. Более подробно, эта программа
(множество инструкций) такова:
Начинай вычисления с 1 и никогда не останавливайся. Добрав-
,-', шись до очередного числа п, запиши в список имя объекта f(n).
(Если же /(п) не определено, то оставь n-ю позицию списка пу-
пустой.)
Но нет никакой необходимости апеллировать к списку или же к
сверхчеловеку-перечислителю: что бы мы ни захотели высказать
относительно счетности, мы можем сформулировать это на язы-
языке самих функций; например, чтобы сказать, что множество Р*
несчетно, нужно просто объявить, что не существует функции на
множестве натуральных чисел, для которой Р* является множе-
множеством значений.
Живые рассуждения о списках и перечислителях со сверхчело-
сверхчеловеческими возможностями могут, правда, стимулировать вообра-
воображение, однако использование подобной терминологии превраща-
превращает теорию счетности и диагонализации в раздел математической
теологии. Чтобы не наступать никому на мозоли, мы могли бы
воспользоваться представлениями древних греков: Кантор доказал
существование множеств, которые не сумел бы перечислить даже
Зевс независимо от того, как быстро или как долго (пусть даже
бесконечно долго) он бы работал.
Если какое-либо множество является счетным, то Зевс может
его перечислить за одну секунду, выписывая бесконечный список
этого множества все быстрее и быстрее. На первый элемент спис-
списка он затратил бы полсекунды, на второй — четверть секунды,
на третий — одну восьмую, и, вообще, каждый следующий эле-
элемент он выписывал бы вдвое быстрее, чем предыдущий. Какой
бы момент внутри секундного интервала мы ни взяли, весь спи-
список к этому времени готов быть не может, но по истечении всей
30
2. Диагонализация
секунды список был бы закончен! В табл. 2-2 представлен ход это-
этого процесса на временной шкале с делениями в одну шестнадцатую
секунды.
Таблица 2-2
0 сек
А
ft
ft
ft
*
¦re
ft -
10
16
tt
Й
if
tt
if
1 сек
Зевс выписывает первый элемент списка
Зевс выписывает второй элемент
Зевс выписывает третий элемент
Зевс выписывает четвертый элемент
Рассуждая о создании бесконечных списков (например, мно-
множества всех натуральных чисел в десятичной записи), приходит-
приходится говорить о перечислителях, либо работающих все быстрее и
быстрее (как выше), либо использующих для завершения списка
все бесконечное время (например, выдавая по элементу в секун-
секунду). Конечно, если бы Зевс поставил перед собой задачу выписать
бесконечную последовательность бесконечных же списков, он мог
бы за одну секунду справиться со всей работой. Он просто выде-
выделил бы первую половину секунды на выписывание всего первого
списка (четверть секунды на первый элемент, одна восьмая се-
секунды на второй и т.д.), второй список выписал бы за следующую
четверть секунды (одна восьмая секунды на первый элемент, одна
шестнадцатая на следующий и т.д.), и, вообще, каждый следую-
следующий список он выписывал бы вдвое быстрее, чем предыдущий, так
что по прошествии секунды у него по порядку были бы выписа-
выписаны все элементы всех списков. При этом полученный результат
2. Диагонализация
31
нельзя было бы рассматривать как единый бесконечный список в
принятом нами смысле. При нашей концепции списка каждый эле-
элемент в нем отделен от первого элемента лишь конечным числом
других.
Если придерживаться нашего понимания термина «список», то
Зевс, выписывая бесконечно много списков один за другим, не созда-
создает тем самым единый список. Однако он мог бы, конечно, создать
настоящий список, содержащий все элементы всех этих списков,
воспользовавшись для этого процедурой, подобной той, которую
в гл. 1 мы применили для перечисления всех положительных ра-
рациональных чисел. Для этого ему достаточно было бы вообразить
бесконечный прямоугольный массив, n-я строка которого при про-
произвольном п представляла бы собой n-й из его списков. Он мог
бы затем выбирать различные элементы из различных списков в
каком-либо из порядков, указанных в табл. 2-3.
(а)
1
4
9
2
3
8
5
6
7
Таблица 2-
(Ь)
1
3
6
10
3
2
5
9
4 7
8 •
В результате получился бы единый список, в котором каждый
элемент каждого из исходных списков появлялся бы на том или
ином конечном месте от начала. Однако канторов диагональный
метод показывает, что ни этот, ни иной, более хитроумный, ме-
метод не позволяют — даже богу! — расположить все множества
натуральных чисел в единый бесконечный список. Такой список
невозможен в той же степени, как и квадратура круга: невозмож-
невозможность перечисления всех множеств натуральных чисел столь же
абсолютна, как и невозможность нарисовать круглый квадрат2, —¦
даже для Зевса.
2 Напомним читателю, что квадратурой круга называется задача о постро-
построении с помощью циркуля и линейки квадрата, равновеликого данному кругу.
Хорошо известно, что эта задача неразрешима. — Прим. персе.
32
Упражнения
2. Диагонализация
2.1. Для данного списка L множеств Si, S2, ¦ • .следующим обра-
образом определим множество D(L):
произвольное натуральное п входит в D(L) тогда и только то-
тогда, когда оно входит в Sn ¦
Пусть L — перечисление всех конечных множеств натуральных
чисел, описанное в решении упр. 1.5. (а) Что представляет собой
множество D(L)? (b) Входит ли D(L) в L? (с) Что есть D(L)?
2.2. Соответствующим образом приспособив диагональный ме-
метод (см. табл. 2-1), докажите, что множество всех действительных
чисел, лежащих на интервале @,1), несчетно. Указание. Каждое
такое число одним или двумя способами представимо в виде бес-
бесконечной десятичной дроби (например, 0.5 = 0.5000 ... = 0.4999 ...,
а 0.123 = 0.123000... = 0.122999...), причем если последователь-
последовательность цифр после точки не заканчивается бесконечной серией нулей
или девяток, то такое представление (т.е. бесконечная последова-
последовательность цифр) единственно.
2.3. С помощью диагональных рассуждений докажите, что мно-
множество всех функций на множестве натуральных чисел с натураль-
натуральными же значениями, определенных всюду или частично, несчетно.
2.4. Определим слово как произвольную конечную последо-
последовательность букв из некоторого счетно бесконечного алфавита
ai, 02, .... Докажите счетность каждого из следующих множеств:
(a) двухбуквенных слов;
(b) трехбуквенных слов;
(c) n-буквенных слов для произвольного фиксированного п;
(d) всех слов произвольной (конечной) длины.
Решения
2.1. Последовательными элементами списка L служат множе-
множества Si = {1}, S2 = 0, 53 = {1,2}, Si - {1} и т.д. Условие п € 5„
выполняется только для п = 1, так как индекс п растет намного бы-
быстрее, чем наибольший элемент множества Sn (который никогда не
бывает больше длины соответствующей последовательности плю-
плюсов и минусов). Поэтому
2. Диагонализацим
33
(a) D(L) = {1}; ^*¦
(b) D(L) входит в L, например, D(L) = Si и D(L) = 54; '
(c) D(L) = {2,3,4,...}, так что D(L) бесконечно и потому не входит
в L, как было уже установлено диагональными рассуждениями для
произвольного случая.
2.2. Пусть L — произвольный список, всякий элемент которого
представляет собой бесконечную десятичную дробь с нулевой целой
частью. Пусть последовательными цифрами в n-м элементе служат
Sn(l), «nB), ..., так что фактически элементы списка L совпадают
со строками табл. 2-1 (при этом теперь каждый элемент таблицы
есть одна из цифр 0, ..., 9). Полагая, что d — любая из десяти
цифр, положим
d' =
если d = 2,
в противном случае.
(Главное в нашем определении — то, что O^d' ф d.) Пусть теперь3
D(L) есть последовательность цифр si(l)', «2B)', ... Эта после-
последовательность не может совпадать ни с одной строкой табл. 2-1,
потому что если бы она совпадала, скажем, с n-й строкой, то мы
имели бы sn(n)' = sn_(n), что противоречит определению операции'.
Теперь, поскольку D(L) не содержит ни нулей, ни девяток, число,
задаваемое этой последовательностью, не совпадает ни с одним из
чисел, заданных списком L. Таким образом, никакой список L дей-
действительных чисел из единичного интервала не может быть исчер-
исчерпывающим.
2.3. Пусть L = /i, /2,... — некоторое перечисление таких функ-
функций. Определим антидиагональную функцию4 ы (= D(L)) следую-
следующим образом:
/ \ _ Г 1, если /п(") не определено,
\ /п(я) + 1 в противном случае.
Таким образом, и есть всюду определенная на множестве натураль-
натуральных чисел функция, принимающая натуральные же значения. Но
3 Авторы допускают здесь небольшую вольность в обозначениях. Обозначе-
Обозначение D(L) использовалось до этого момента как имя антидиагонального множе-
множества (построенного по соответствующему списку). Сейчас оно применяется для
обозначения антидиагональной последовательности (с тем очевидным измене-
изменением, что в соответствующем массиве размещаются произвольные цифры, а не
только нули и единицы). — Прим. перев.
И здесь D(L) понимается несколько вольно. — Прим. перев.
3-249
34
2. Диагонализациж
2. Диагонализациж
35
она не может содержаться в списке L: если бы, скажем, выполня-
выполнялось и = /т, то из определения следовало бы, что
fm(m) = и(т)
-I1'
если fm(m) не определено,
(т) + 1 в противном случае.
Теперь независимо от того, приписывает функция fm какое-либо
значение аргументу т или нет, мы получаем противоречие: если
/m(m) не определена, она оказывается определенной (и принимаю-
принимающей значение 1), если же /m(m) определена и равна, скажем, п, то
получается равенство п = п + 1.
2.4. Решение «в лоб» использует прием (вновь и вновь!), при-
примененный нами при перечислении положительных рациональных
чисел.
(а) Образуем прямоугольный массив двухбуквенных слов, как это
показано в табл. 2-4(а), и проложим наш путь по ней, например,
по треугольникам, как предлагается в табл. 2-3(Ь); в результате
получится единый список
aiai, aia2, a2ai, aia3, 0^02, 0301,
Таблица 2-4
¦>&¦
(Ь)
a2
a3
aiai Q\CL%
a2ai a2a2
азах аза2
a3
СНОЗ ...
fit 2^3 . . •
0303 . ».
-}« м .
' ¦ t ¦¦'•!!
a2
аз
v. /,> *
(b) Чтобы перечислить все трехбуквенные слова, заметим, что ка-
каждое из них получается приписыванием некоторого двухбуквенно-
го слова к некоторому однобуквенному. Образуем массив, пред-
представленный в табл. 2-4(Ь), и по треугольникам, как указано в
табл. 2-3(Ь), проложим наш путь по нему для получения требуе-
требуемого списка
(c) Чтобы перечислить четырехбуквенные слова, обойдите анало-
аналогичным образом массив, у которого столбцы помечены трехбуквен-
трехбуквенными словами, а строки — однобуквенными. Далее продолжайте
аналогичным образом. Итерируя эту процедуру нужное число раз,
вы сможете перечислить n-буквенные слова для произвольного фик-
фиксированного п.
(d) Чтобы перечислить все слова произвольной конечной длины,
обойдите указанным образом массив, в котором первой строкой слу-
служит список всех однобуквенных слов а\, а2, ..., второй строкой —
список всех двухбуквенных слов (см. п. (а)), третьей — список всех
трехбуквенных слов (см. п. (Ь)) и т.д.
Существует, однако, более простой прямой способ, позволяю-
позволяющий построить список (правда, с пробелами) всех слов произволь-
произвольной конечной длины в алфавите а\, аг, .... Чтобы определить в
этом списке положение произвольного такого слова, заменим ка-
каждое вхождение буквы ах в это слово числом 12, каждое вхожде-
вхождение а2 — числом 122 и, вообще, каждое вхождение буквы а„ —
единицей с п двойками вслед за ней. Результатом служит конечная
последовательность цифр; натуральное число, десятичной записью
которого она служит, будем считать номером исходного слова в
нашем списке. (Таким образом, этот список начинается с одинна-
одиннадцати пробелов. Первым, на двенадцатом месте, в нем встречается
однобуквенное слово а\. Следующее слово в списке — это а2, сто-
стоящее на 122-м месте. Третьим идет слово a^ai, стоящее на 1212-м
месте. Четвертое слово — это аз, на 1222-м месте.) Подобным же
образом (и даже проще) можно получить список n-буквенных слов
для любого фиксированного п.
Машины Тьюринга
Никакое человеческое существо не способно писать достаточно
быстро, достаточно долго или достаточно мелко1 для того, что-
чтобы выписать одно за другим имена (в некоторой системе обозна-
обозначений) всех элементов некоторого счетно бесконечного множества.
Но для некоторых счетно бесконечных множеств в человеческих
силах сделать нечто равно полезное: можно сформулировать яв-
явные инструкции, позволяющие для произвольного п определять п-й
элемент данного множества. Такие инструкции должны быть пре-
предельно четкими и иметь такую форму, чтобы им могла следовать
вычислительная машина или же человек, способный к выполнению
только очень элементарных операций над символами. Конечно, из-
за ограничений на время, отпущенное на вычисления, на скорость,
с которой выполняются элементарные шаги этих вычислений, и
на количество материи в мире, доступной для создания символов,
остается проблема, что как для человека, так и для машины физи-
физически осуществимы вычисления лишь для конечного числа значе-
значений п. Однако из соображений простоты и ясности мы игнорируем
эти ограничения и будем, таким образом, работать с понятием вы-
вычислимости, превосходящим реальные возможности человека или
машины. Главное — это чтобы наше понятие вычислимости не ока-
оказалось слишком узким, поскольку уже вскоре мы будем его исполь-
использовать для доказательства невычислимости некоторых функций, а
также того факта, что некоторые счетные множества не являются
эффективно (механически) перечислимыми — даже если разреше-
разрешено каким-либо образом обходить физические ограничения на время,
скорость и количество требующегося материала.
Понятие вычисления можно уточнять многими различными спо-
способами в зависимости от того, какие из возможных ответов бу-
будут даны на следующие вопросы. На каком носителе выполняет-
выполняется вычисление: на одномерной ленте, на прямоугольной решетке
1 На свете ведь имеется лишь конечное количество бумаги, так что вам при-
придется писать все мельче и мельче, без предела, чтобы бесконечное число симво-
символов уместить на этой бумаге. В конце концов вам придется писать на молекулах,
на атомах, электронах ....
3. Машины Тьюринга
37
или на чем-то еще? Если используется лента, то какая: имею-
имеющая начало, но не имеющая конца или же бесконечная с обеих
сторон? Обладают ли адресами (подобно адресам домов на ули-
улице) клетки, на которые разделена лента, или же память о том,
где мы находимся, должна записываться с помощью специаль-
специальных символов в соответствующих клетках (подобно тому, как до-
дорогу в лесу можно отмечать, маркируя деревья)? И так далее.
В зависимости от того, какие ответы будут даны на эти во-
вопросы, понятие вычисления, если говорить о деталях, приобре-
приобретет тот или иной вид. Наша задача, однако, состоит вовсе не
в том, чтобы дать точное изображение отдельных шагов, из ко-
которых складывается вычисление, и, более того, класс функций,
допускающих вычисление, оказывается, не зависит от того, ка-
какие ответы будут получены на эти вопросы. Поэтому теперь, же-
желая дать некоторую характеристику классу вычислимых функ-
функций, мы некоторым образом ответим на эти и другие вопросы.
Имеющийся опыт работы с понятием вычислимости наводит на
мысль, что основное содержание этого понятия не зависит от то-
того, какие — достаточно правдоподобные — ответы будут при-
приняты. Действительно, если взять любое другое точное и прав-
правдоподобное определение понятия вычисления из тех, которые бы-
были предложены, то можно аккуратно и строго доказать, что на-
наше понятие вычислимости эквивалентно новому в том смысле,
что всякая функция, вычислимая согласно одному из них, оказы-
оказывается вычислимой и согласно другому. Но так как нет преде-
предела возможным вариациям в точном определении понятий вычи-
вычислимости и эффективности, то следует в конце концов принять
или отвергнуть тезис (не допускающий математического дока-
доказательства) о том, что множество функций, вычислимых в на-
нашем смысле, совпадает с множеством функций, доступных для
вычисления машинами и людьми с использованием произволь-
произвольных эффективных методов, если только игнорируются ограниче-
ограничения, связанные с нужными временем, скоростью и материалом.
Хотя этот тезис (известный как тезис Чёрча) недоказуем, он
был бы опровержимым, если бы оказался ложным. Действитель-
Действительно, если он ложен, то существует функция, вычислимая в инту-
интуитивном смысле, но не вычислимая с нашей точки зрения. Что-
Чтобы установить вычислимость такой функции в интуитивном смы-
смысле, достаточно привести инструкции для вычисления ее значений
для всех возможных значений аргумента и убедиться, что эти
38
3. Машины Тьюринга
инструкции действительно эффективны. (Предполагается, что в
отдельном конкретном случае мы можем установить, что множе-
множество инструкций эффективно.) Чтобы убедиться, что такая функ-
функция не является вычислимой в определяемом нами смысле, нуж-
нужно просмотреть всевозможные машины Тьюринга [соответствую-
[соответствующие определения будут даны позже. — Перев.] и проверить (с по-
помощью соответствующих доказательств), что ни одна из них не
вычисляет рассматриваемую функцию. (В гл. 4 и 5 мы вкрат-
вкратце рассматриваем примеры таких доказательств; однако функ-
функции, про которые там доказано, что они не могут быть вычи-
вычислимыми по Тьюрингу, не могут оказаться вычислимыми ни в
каком интуитивном смысле, так что они не являются контрпри-
контрпримерами для тезиса Чёрча.) Поэтому, если бы тезис Чёрча был
ложным, он опровергался бы с помощью контрпримера; и чем
больший опыт по части вычислений накапливается нами в от-
отсутствие подобных контрпримеров, тем больше это подтверждает
тезис Чёрча.
Перейдем к деталям. Будем предполагать, что вычисление осу-
осуществляется на ленте, разделенной на клетки и бесконечной в обоих
направлениях — последнее понимается либо как актуальная, дей-
действительная бесконечность, либо как наличие при каждом из ее
концов специального человека, добавляющего к ленте пустые клет-
клетки по мере надобности. Как вначале, так и в любой из последующих
моментов вычисления все клетки ленты, кроме конечного их коли-
количества, пусты. Если какая-либо клетка непуста, то в ней записан
точно один из конечного числа символов Si, ..., Sn. Удобно счи-
считать, будто в пустой клетке записан специальный пустой символ,
или бланк. Этот символ мы обозначим So-
На каждом шаге вычисления вычислитель (человек или меха-
механическое устройство) обозревает одну из клеток ленты. Он раз-
различает, который из символов записан в обозреваемой им клетке.
Он может стереть записанный в обозреваемой клетке символ и за-
записать там новый символ. Возможны также передвижения — на
одну клетку вправо или на одну клетку влево. Если вам угод-
угодно, вы можете грубо представлять себе машину как коробочку
на колесах, находящуюся в каждый момент вычисления над од-
одной из клеток ленты. Ленту можно уподобить полотну железной
дороги, шпалы обозначают границы клеток, а наша машина похо-
похожа на очень короткий вагон, который может двигаться по рель-
рельсам в обоих направлениях, как показано на рис. 3-1. На дне
3. Машины Тьюринга
39
вагончика имеется устройство, умеющее читать, что записано меж-
между шпалами, стирать записанное там и записывать новые симво-
символы.
Рис. 3-1
> Машина устроена так, что в каждый момент вычисления она
находится в одном из конечного числа внутренних состояний
91) • • •, 9т • Пребывание машины в том или ином состоянии может
иметь тот смысл, что тот или иной зубец какой-либо шестерен-
шестеренки занимает в соответствующий момент верхнее положение, или
что электрическое напряжение в некоторой определенной точке на-
нашего устройства принимает то" или иное из m возможных значе-
значений, или что угодно еще: нас не интересует конкретное механиче-
механическое или электрическое устройство машины. Проще всего, может
быть, обрисовать картину самым грубым образом: внутри ящи-
ящика находится человек, который и выполняет все считывания, за-
записывания, стирания (символов) и передвижения. (Ящик при этом
не должен иметь дна: бедняга, таким образом, топает вдоль пу-
пути между шпалами, таская свой ящик на себе.) У этого человека
имеется список из т инструкций, записанных на листе бумаги. Он
находится в состоянии д,-, когда выполняет инструкцию с номе-
номером i.
Каждая инструкция имеет условный характер: она говорит че-
человеку, что ему делать в зависимости от считываемого символа
(т.е. в зависимости от того, записан в считываемой клетке сим-
символ So, или Si, или ..., или Sn). Предписываемое действие может
иметь один из п 4- 4 видов:
A) Остановить вычисление.
B) Сдвинуться на одну клетку вправо.
C) Сдвинуться на одну клетку влево.
D) Записать в считываемую клетку символ So вместо того, что
там было.
40
S. Машины Тьюринга
E) Записать в считываемую клетку символ Si вместо того, что
там было.
(п + 4) Записать в считываемую клетку символ Sn вместо того,
что там было.
Так, в зависимости от того, какую инструкцию он выполняет
(= в каком состоянии он находится) и какой им считывается сим-
символ, человек будет выполнять то или иное из этих п + 4 наблю-
наблюдаемых действий. И вплоть до момента остановки (наблюдаемое
действие номер 1) он будет также под покровом своего ящика вы-
выполнять по одному скрытому действию на каждый шаг вычисле-
вычисления — а именно, он будет определять, какой окажется следующая
инструкция (следующее состояние). Итак, текущее состояние и
считываемый в тот же момент символ определяют, какое долж-
должно быть выполнено наблюдаемое действие и каким должно быть
следующее состояние.
Вся программа, состоящая из инструкций, которым наш человек
должен следовать, может быть описана различными способами, на-
например с помощью машинной таблицы или же графа переходов
или как множество четверок. Три этих способа описания про-
продемонстрированы на рис. 3-2 для случая машины, пишущей на
пустой ленте три символа Si и после этого останавливающейся,
так что считываемым оказывается самый левый символ из трех.
Пример 3.1. Записать S^S^S^
Определяемая машина будет писать символ Si в клетке, считы-'
ваемой ею в начальный момент, сдвигаться на один квадрат влево,
записывать в него Si, сдвигаться влево еще на один квадрат, вписы-
вписывать в него третий символ Si и останавливаться. (Она останавли-
останавливается, когда не имеет дальнейших инструкций.) У нее будет три
состояния — по одному для каждого из символов Si, которые долж-
должны быть написаны. Записи в верхней строке (под горизонтальной
чертой) машинной таблицы, приведенной на рис. 3-2, говорят, что,
следуя инструкции q\, нужно A) записать символ Si и вернуться
к выполнению инструкции qx, если считывается символ So, но B)
если считывается символ Si, то нужно сдвинуться влево и перейти
к выполнению инструкции q?. Та же информация закодирована в
графе переходов с помощью двух стрелок, выходящих из вершины,
обозначенной qi. Наконец, эта же информация содержится в первых
3. Машины Тьюринга
41
Считываемый
символ
1
&
1
8
:ос
91
92
93
So
Si?i
Si 92
Si 93
Si
Lq2
?93
So:Si
(а) Машинпам .^' (b) Граф переходов
таблица
Рис. 3-2
92 So Si 92, 92 Si Lqa,
93 So Si 93
(с) Множество ,
четверок
(верхних) двух четверках в описании (с) данной машины. Смысл
элемента машинной таблицы, стрелки в графе переходов, равно как
и четверки, разъяснен на рис. 3-3.
Действие
Считыв..Дейст-
символ * вие
Та же
последовательность,
что и для стрелок
(а) Элемент таблицы (Ь) Стрелка в графе переходов (с) Четверка
Рис. 3-3
Если не оговорено противное, будем считать, что машина на-
начинает работу в состоянии с наименьшим номером. Рассматривае-
Рассматриваемая машина останавливается, если в состоянии <?з она считывает
символ Si, поскольку в ее таблице нет записи (соответственно нет
стрелки в графе переходов, равно как и четверки), говорящей, что
следует делать в таком случае.
Способ представления машинных программ с помощью графов
переходов обладает тем преимуществом, что если только начальное
состояние каким-либо способом указано (например, если оно будет
изображаться самой левой вершиной, за исключением случая, ко-
когда оговорено противное), то можно отказаться от использования
названий состояний: не имеет значения, как вы их назовете. Тогда
граф переходов можно изобразить так, как это сделано на рис. 3-4.
Показать, как такая машина работает, можно с помощью последо-
последовательности ее конфигураций. Каждая конфигурация показывает,
что записано на ленте во время выполнения некоторого шага вычи-
вычисления, а также в котором из состояний находится машина на этом
шаге и какая клетка при этом ею считывается. Будем изображать
эту информацию, приводя имеющуюся на ленте запись и указывая
42
S. Машины Тьюринга
So-.St
¦L Q SuL
'f. \<.<'
Рис. 3 — 4. Напишите три символа Sj. ¦ ¦
текущее состояние под символом, расположенным в считываемой
клетке:
0000000, 0000100, 0000100, 0001100, 0001100, 0011100.
1 ' 1 ' 2 ' 2 3 ' 3
Мы заменили здесь символы So и Si на 0 и 1 соответственно, обо-
обозначив аналогичным образом состояния q\, q% и дз через 1, 2 и 3,
чтобы избежать ненужной громоздкости. Таким образом, напри-
например, последняя конфигурация есть сокращенная запись для
.« - ¦'-,¦¦ SqSqS\S\S\SoSo- .-.'.. , , , .;¦> '¦%¦
Разумеется, последовательности символов So в начале и конце лен-
ленты могут быть по желанию укорочены или удлинены без изменения
сути дела: можно считать, что лента на каждом из концов имеет
столько пустых символов, сколько вам угодно.
Перейдем теперь к более сложному примеру. !;"-....',
Пример 3.2. Удвоение числа единиц * ' г'"ш- '
Эта машина начинает работу, считывая самый левый символ в
конечной последовательности единиц на ленте с пустыми символа-
символами во всех остальных клетках, и останавливается, считывая самый
левый символ во вдвое более длинной, чем исходная, последователь-
последовательности единиц на ленте с пустыми символами в остальных клетках.
На следующей странице изображен граф переходов этой машины.
Как она работает? Грубо говоря, она приписывает по две единицы
слева, стирая при этом по одной единице справа. Более конкретно,
предположим, что исходной служит конфигурация 111, так что мы
начинаем в состоянии 1, считывая самую левую единицу в строчке
из трех единиц на ленте с пустыми символами во всех остальных
клетках. Следующие несколько конфигураций таковы:
0111, 00111, 10111, 010111, 110111.
2 3 ' 3 ' 4 '4
3. Машины Тьюринга
0-.R
43
0:1 0:1 1-Я 1-Я 1:0
Итак, мы записали слева первую пару единиц, отделенную от ис-
исходной последовательности, 111, символом 0. Затем мы движемся
вправо мимо этого нуля к правому концу исходной строчки единиц
и стираем самую правую из них. Вот эти действия, разложенные
на два этапа. Этап 1:
110111, 110111, 110111, 110111, 110111, 1101110.
5 5 6 6 6 6
Теперь мы знаем, что перешли через самую правую из данных еди-
единиц, и потому (этап 2) поворачиваем назад и стираем ближайшую
единицу: '
110111, 110110.
7 7
Теперь мы возвращаемся к нашему начальному положению, к са-
самой левой единице, оставшейся от исходной строчки. Проделав эту
петлю еще раз, мы придем к конфигурации 1111010. Теперь прохо-
проходятся следующие конфигурации:
111101,
8
0111101,
ю
111101,
111101,
111101,
0111101,
з
111101,
1111101,
з
111101,
ю
111101,
10
01111101,
11111101.
4
Нужные шесть единиц уже на ленте, но нам требуется еще стереть
последнюю единицу из трех исходных и остановиться, считывая
самую левую из шести написанных нами. Вот как это делается:
11111101, 11111101,
5 '5
11111101, 11111101, 11111101,
5 ' 5 б'
111111010, 11111101, 11111100, 1111110, 111111,
6 7 7 8' 11
111111,
111111, 0111111, 111111.
11 11 12
44
3. Машины Тьюринга
Мы достигли состояния 12, считывая при этом 1. Поскольку в гра-
графе переходов нет стрелки из этой вершины, показывающей, что
делать в таком случае, мы останавливаемся. Машина делает то,
что было объявлено. (Замечание. Тот факт, что машина удвоила
число единиц, когда вначале их было три, не доказывает, что ма-
машина совершает те изменения, что были обещаны, в общем случае.
Однако в нашем исследовании частного случая, когда первоначаль-
первоначально имелось три единицы, не использовался существенно тот факт,
что их было три: оно без труда превращается в доказательство то-
того, что машина удваивает число единиц при любом их начальном
количестве.)
Пример 3.3. Написать на чистой ленте an единиц и оста-
остановиться, считывая самую левую из них
Задача допускает решение «в лоб» с использованием 2п состо-
состояний. Будем действовать тем же способом, что и в примере 3.1.
Граф переходов нужной машины получается последовательным со-
0:1
единением «в цепочку» 2п экземпляров узла ( j > , причем послед-
последняя стрелка обрубается. Но есть и другой путь, требующий всего
п + 11 состояний: на ленте непосредственно пишется п единиц, по-
после чего, как в примере 3.2, этот массив удваивается. Схематиче-
Схематически: мы соединяем два графа переходов, отождествляя вершину 1
из примера 3.2 с вершиной п из графа машины, пишущей п единиц
на пустой ленте. Бели число п велико, то первое решение рассма-
0:1
0:1
,,,
CrULC3l:L 1:.
Напишите п символе» 1
Граф из
примера
3.2
Удвойте это
триваемой задачи требует значительно большего числа состояний,
чем непрямой путь, только что описанный нами. (Если п > 11, то
2п > п + 11.) Можно было бы, конечно, сэкономить еще больше со-
состояний, дважды применив процедуру удвоения; например, чтобы
S. Машины Тьюринга
45
записать 100 единиц, можно было бы с помощью 25 состояний запи-
записать сначала 25 единиц, затем с помощью 11 состояний удвоить их
число и, наконец, путем удвоения только что полученного масси-
массива с помощью еще 11 состояний получить окончательные 100 еди-
единиц. Таким способом результат достигается с использованием все-
всего 47 состояний вместо 100 состояний, нужных для применения
прямого метода, или 61 состояния, требующегося при однократ-
однократном применении процедуры удвоения.
Упражнения. (Решения приведены после списка упражнений.)
3.1. Постройте машину Тьюринга, которая, начиная работу в
самой левой клетке конечной сплошной последовательности единиц
на ленте, где во всех клетках, кроме занятых этой последователь-
последовательностью, стоят пустые символы, остановилась бы в конце концов на
некоторой клетке, в которой записаны пустой символ или единица
в зависимости от того, было исходное число единиц четным или
нечетным (все остальные клетки ленты в заключительной конфи-
конфигурации содержат пустые символы).
3.2. Постройте машину Тьюринга, которая, начиная работу в
самой левой клетке конечной сплошной последовательности из еди-
единиц и двоек (записанных в любом порядке и количестве, вплоть до
того, что вся строчка может состоять из одних единиц или из одних
двоек) на ленте с пустыми символами во всех остальных клетках,
остановилась бы в конце концов в какой-то точке, так чтобы по
записи на ленте можно было бы определить (в соответствии с усло-
условиями, которые вы можете задать сами), было в исходной строчке
одинаковое количество единиц и двоек или нет.
3.3. Прибавление единицы в десятичной записи. Вначале маши-
машина считывает самую правую клетку конечной сплошной последо-
последовательности из десятичных цифр, записанной на ленте с пустыми
символами во всех остальных клетках. Когда она останавливает-
останавливается, на ленте должно быть записано десятичное представление чи-
числа, на единицу большего, чем исходное. Постройте по возможно-
возможности простую машину, которая это делает. (Приведите машинную
таблицу — граф переходов может оказаться неудобным для воспри-
восприятия.)
3.4. Умножение чисел, записанных в виде массивов единиц. В
начальный момент лента пуста, не считая двух сплошных блоков
из единиц, разделенных единственным пустым символом. Пусть
в первом блоке содержится р единиц, а во втором q. Постройте
46
S. Машины Тьюринга
машину, которая, начиная работу с самой левой единицы ва лен-
ленте, останавливалась бы на самой левой клетке сплошного блока
из pq единиц на ленте с пустыми символами во всех остальных
клетках.
3.5. Сложение в той же системе записи. (Все то же, что и в
упр. 3.4, с заменой pq на р + q.)
3.6. Не все функции на множестве натуральных чисел с на-
натуральными же значениями вычислимы по Тьюрингу. Из одного
из упражнений к гл. 2 вы уже знаете, что таких функций суще-
существует намного больше, чем машин Тьюринга, так что должны
существовать функции, не вычисляемые ни одной машиной Тью-
Тьюринга. Объясните это более подробно.
3.7. Продуктивность. Рассмотрим машины Тьюринга, исполь-
использующие помимо пустого символа единственный символ 1. В на-
начальный момент лента пуста. Если машина в конце концов оста-
останавливается, считывая при этом самый левый символ сплошного
массива единиц на ленте с пустыми символами во всех остальных
клетках, то ее продуктивностью называется длина этого массива.
Если же машина не останавливается вовсе или останавливается
в какой-нибудь иной конфигурации, то ее продуктивность счита-
считается равной нулю. Пусть теперь р(п) есть продуктивность са-
самой продуктивной машины Тьюринга с п состояниями. Докажите,
что
(a) рA) = 1;
(b) рD7) > 100;
(c) р(п + 1) > р(п);
(d) p(n+ 11) >2п. '
(По поводу решения см. гл. 4.)
3.8. Проблема усердного бобра (см. Rado Tibor, Bell System
Technical Journal, may 1962). Согласно упр. 3.6, невычислимые
функции существуют. Но как могла бы выглядеть такая функ-
функция? Оказывается, одну из них вы уже видели: это функция р,
определенная в упр. 3.7. Доказательство ее невычислимости осно-
основывается на том факте, что «проблема усердного бобра» нераз-
неразрешима. Проблема эта состоит в том, чтобы построить маши-
машину Тьюринга, использующую только пустой символ и единицу,
которая, начиная работу в состоянии 1 и считывая при этом
самый левый символ сплошного массива из п единиц на лен-
ленте с пустыми символами во всех остальных клетках, останавли-
останавливалась бы в конце концов на самом левом символе сплошного
3. Машины Тьюринга
47
массива из р(п) единиц на ленте с пустыми символами во всех
остальных клетках. Оказывается, что такой машины не суще-
существует. Для доказательства предположим, что такая машина су-
существует (и имеет, скажем, к состояний), и выведем отсюда
противоречие. Для этого нужна определенная изобретательность.
Указание. Если бы такая машина существовала, то, присоеди-
присоединяя последовательно два экземпляра этой машины к машине с
п состояниями, записывающей на пустой ленте п единиц (спра-
(справа налево), вы получили бы машину с n + 2ib состояниями, про-
продуктивность которой равнялась бы р(р(п)), а отсюда, используя
два последних пункта из упр. 3.7, можно вывести противоре-
противоречие.
Напишите п
символе» 1
Машина
усердного бобра
Машина
усердного бобра
(По поводу решения см. гл. 4.)
3.9. Невычислимость с точки зрения диагонализации. Вся-
Всякая машина Тьюринга, использующая в качестве символов толь-
только пустой символ и единицу, в следующем смысле вычисляет
некоторую функцию на множестве натуральных чисел с нату-
натуральными же значениями: для вычисления такой функции при
значении аргумента г» машина начинает работу в состоянии с
наименьшим номером, считывая при этом самую левую клет-
клетку последовательности из п единиц на ленте с пустыми симво-
символами во всех остальных клетках. Функция определена для это-
этого значения аргумента тогда и только тогда, когда машина в
конце концов останавливается, считывая при этом самую ле-
левую клетку конечной сплошной последовательности из единиц на
ленте с пустыми символами во всех остальных клетках; зна-
значением функции в. таком случае служит длина окончательной
последовательности из единиц. Поскольку множество всех ма-
машин Тьюринга счетно (см. упр. 3.6), так же обстоит дело и
с функциями, вычисляемыми этими машинами. Определите те-
теперь «антидиагональную» функцию и докажите, что не существу-
существует вычисляющей ее машины Тьюринга. (По поводу решения см.
гл. 5.)
3.10. Проблема остановки. Пусть М\, Мг, ... — некоторая ну-
нумерация всех машин Тьюринга, использующих в качестве символов
48 S. Машины Тьюринга
только пустой символ и единицу. Проблема самоприменимости
состоит в том, чтобы построить некоторую эффективную про-
процедуру для вычисления (возможно, частичной) функции s, опре-
определяемой условием: s(n) = 1 тогда и только тогда, когда маши-
машина Мп никогда не остановится, если ее запустить в начальном
состоянии на самой левой единице в сплошной последовательно-
последовательности из п единиц при пустых символах в остальных клетках лен-
ленты. Полная проблема остановки состоит в построении эффектив-
эффективной процедуры для вычисления функции Л, определяемой усло-
условием: h(m, п) = 1 тогда и только тогда, когда машина Мп ни-
никогда не останавливается, если ее запустить в ее начальном со-
состоянии на самой левой единице сплошной последовательности из
п единиц при пустых символах во всех остальных клетках лен-
ленты.
(a) Докажите, что проблема самоприменимости неразрешима. ,>
(b) Докажите такое следствие: проблема остановки неразрешима.:
Указание. Рано или поздно придется использовать тезис Чёрча.
Рано и поздно: докажите, что одна из функций, про которые в
упр. 3.6 было показано, что они не могут вычисляться ни одной
машиной Тьюринга, оказалась бы вычислимой в несколько нестан-
нестандартном смысле (при одновременном использовании двух машин
Тьюринга), если бы проблема самоприменимости была разреши-
разрешимой.
Решения
(Мы пишем В
вместо пустого символа So.)
8.1. Если вначале на ленте имеется 0, или 2, или 4, или ...
единиц, то эта машина останавливается в состоянии 1, считывая
при этом пустой символ на пустой ленте; если же вначале име-
имелось 1, или 3, или 5, или ... единиц, то она остановится в состоя-
состоянии 5, считывая при этом символ 1 на ленте с пустыми символами
в остальных клетках.
3. Машины Тьюринга
49
3.2. Когда эта машина (см. рисунок) останавливается, лента
оказывается пустой тогда и только тогда, когда в исходной по-
последовательности символов имелось равное количество единиц и
двоек.
Замените
самый левый
символ 1 на 3
и вернитесь
налево
Замените
самый левый
символ 2 на 3
и вернитесь
налево
Сотрите все
символы 3,
занимающие
самые левые
позиции
Существуют и другие пути, позволяющие добиться того же, на-
например, конструкции, при которых соответствующая машина не
использует иных символов, кроме 1 и 2. Простейший способ до-
добиться этого, совместимый, правда, скорее с буквой, нежели с духом
формулировки нашей задачи, состоит в том, чтобы принять следую-
следующее соглашение о способе кодирования на ленте в момент остановки
машины информации о том, было ли сначала число единиц и двоек
на ленте одинаковым: их количество было одинаковым в началь-
начальный момент в точности тогда, когда на ленте имеется одинаковое
число единиц и двоек в момент, когда машина останавливается.
Такая машина может остановиться сразу же, так что записанное
на ленте по окончании «работы» тождественно тому, что было на
ленте вначале. Граф переходов такой машины мог бы выглядеть
так: (lj.
3.3. В этом случае на ленте может записываться 11 символов, а
именно В (пустой символ), 0 (теперь это цифра «нуль», а не пустой
символ), 1, ..., 9 (обычные цифры). Каждая из пар, заполняющих
таблицу на стр. 50, изображает действие, которое нужно выпол-
выполнить, и следующее состояние (в таком именно порядке). Многочи-
Многочисленные пробелы во втором столбце соответствуют ситуациям, в
которых машина не имеет инструкций и потому останавливается.
4-249
50
S. Машины Тьюринга
Машинная таблица для прибавления 1 в десятичной записи
Считываемый Текущее состояние
символ
В
О
1 ;
2 ¦'•¦
"•¦ ' 3 f
4 .'¦
6
7
8
9
1
1 2
1 2
22
32
42
52
62
72
82
92
02
2
L 1
• t ¦:*¦<
s.', " 1 ' . Ж
т»
3.4. Имеется множество одинаково эффективных способов перем-
перемножения чисел, записываемых в виде массивов единиц. Во многих
из них, помимо пустого символа В и 1, заполняющих ленту в на-
начальной и конечной конфигурациях, появляются вспомогательные
символы, и в этом нет ничего дурного: машина использует эти сим-
символы для хранения информации о том, в какой стадии процесса она
находится, и перед остановкой все их стирает. При предлагаемом
способе, однако, на протяжении всего процесса используются толь-
только В и 1. Это сделано для того, чтобы проиллюстрировать следую-
следующее положение: всякая функция на множестве натуральных чисел
с натуральными же значениями, вычислимая на какой-либо ма-
машине Тьюринга, вычислима при использовании рассматриваемой
системы записи чисел на машине, использующей только символы
Bui.
Вот как работает эта машина. Первый блок, из р единиц, ис-
используется как счетчик для хранения информации о том, сколько
раз машина добавила по q единиц к правой их группе. Начиная
работу, машина стирает самую левую из р единиц и смотрит, оста-
осталась ли в группе-счетчике еще хоть одна единица. Бели нет, то
pq = q и все, что должна сделать машина, — это вывести себя на
самую левую из имеющихся на ленте единиц и остановиться. Бели
же в группе-счетчике остаются единицы, то машина приступает к
выполнению процедуры, называемой нами чехардой: она сдвигает
по ленте блок из q единиц («группу чехарды») на q позиций вправо,
3. Машины Тьюринга
51
В этот момент машина считывает
самую левую 1 на ленте
Сотрите самую левую 1,
еше остающуюся в
группе-счетчике, и
двигайтесь вправо.
Группа-счетчик еще
не пуста. Перейдите
ко второй клетке
справа от нее.
Процедура чехарды
Найдите и сотрите
самую левую 1 в
группе чехарды.
Сдвиньтесь на одну
клетку вправо.
На этом чехарда не
заканчивается, и
потому
Сдвиньтесь на две
клетки вправо от
первого блока единил
в группе чехарды.
Если эта клетка
пуста,запишите в ней
1. Если же это не
так, запишите 1
справа от всей
группы чехарды.
На этом чехарда заканчивается.
:В
B-.R
Группа-счетчик пуста.
Двигайтесь вправо,
записывая 1 по ходу
движения, пока не
^достигнете группы
чехарды.
_ Затем
возвращайтесь
налево и оста-
остановитесь на
самой левой
1 на ленте.
:L
Двигайтесь влево
к началу
группы-счетчика.
Граф-схема умножениж чисел, записанных в виде массивов единиц
что, например, в случае р = 2 и q = 3 изображается преобразовани-
преобразованием начальной ситуации на ленте
11В111
52
S. Машины Тьюринга
в ситуацию
BIBBBB1U,
возникающую после выполнения чехарды. Теперь машина замеча-
замечает, что в группе-счетчике осталась только одна единица, и тогда
стирает эту единицу, сдвигается на две клетки вправо и заменяет
все более правые пустые символы на единицы, пока не доберется
до символа 1; от этого места она движется к самой левой единице
и там останавливается. Вот как работает наша чехарда:
Первая
111 I 1 I 1 11 I I I
Группа-
счетчик
Группа чехарды
Вообще, группа чехарды состоит из блока, содержащего 0 или 1,
или ..., или q единиц, за которым стоит пустой символ со следу-
следующим за ним остатком от q единиц. Этот пустой символ ставится
для того, чтобы сообщить машине об окончании игры в чехарду: без
этого группа из q единиц поехала бы по ленте вправо без конца. (Во
время игры в чехарду группа из q единиц, стоящая в группе чехар-
чехарды слева от пустого символа, функционирует в качестве счетчика:
она контролирует процесс добавления единиц к той части группы
чехарды, что расположена справа от пустого символа. Этим объ-
объясняется, почему в графе переходов имеется две большие петли —
каждая соответствует подпроцедуре, контролируемой некоторым
счетчиком.)
3.5. Нужно всего лишь стереть самую левую единицу, заполнить
пробел между двумя данными блоками единиц и остановиться на
самой левой из единиц, оставшихся на ленте. Вот один из путей вы-
выполнения всего этого (в «четверочной» записи): qiSiSoqi, qiSoRq2,
3.6. Согласно упр. 2.3, множество всех функций, определенных
на множестве натуральных чисел, с натуральными же значения-
значениями несчетно. С другой стороны, множество всех машин Тьюринга
3. Машины Тьюринга
53
является счетным, поскольку всякую машину Тьюринга можно за-
задать конечной последовательностью букв в бесконечном алфавите
;, R, L, So, 91, Si, 92, S2, 93, ••¦ ,
а, согласно упр. 2.4(d) (при а^ =;, а2 = R, a3 — L, а4 = So,
05 = 91, •••)> множество всех таких последовательностей счетно.
(Нам нужно как-нибудь договориться о том, которое из состояний
машины считать начальным; например, можно объявить началь-
начальным состояние 9i-) Теперь, какое бы соглашение мы ни приняли о
том, какая функция должна считаться вычисляющейся произволь-
произвольной машиной Тьюринга из нашего списка (если таковая вообще су-
существует), этот список (нумерация) машин Тьюринга порождает
нумерацию (возможно, с пробелами) всех функций из натуральных
чисел в натуральные, вычисляющихся на машинах Тьюринга в со-
соответствии с принятым соглашением. Возможным вариантом та-
такого соглашения служит описанное в упр. 3.4, согласно которому
можно считать, что машины Тьюринга, определяющие четверки
которых содержат хоть один из символов S2, S3, ..., вообще не
вычисляют функции из натуральных чисел в натуральные2. Заме-
Заметим, что если /i, /2, /3, • • • — не содержащая пробелов нумерация
всех функций, вычислимых по Тьюрингу в соответствии с нашим
соглашением, то антидиагональная функция « из упр. 2.3 служит
примером функции из натуральных чисел в натуральные, не до-
допускающей вычисления (в этом смысле) ни на одной машине Тью-
Тьюринга. Другим примером служит частичная функция t, задаваемая
следующим образом:
1, если Л» (я) не определено,
не определено, если /п(п) определено.
(Дальнейшие детали см. в гл. 5)
3.10(а). Если бы проблема самоприменимости была разреши-
разрешима, то, согласно тезису Чёрча, существовала бы некоторая машина
Тьюринга S, вычисляющая (при некотором соглашении о деталях
этого понятия) функцию s, например вычисляющая ее в смысле
2 Понятие функции, вычисляемой машиной Тьюринга, определено в форму-
формулировке упр. 3.9. Фразу, к которой делается примечание, следует, видимо, по-
понимать в том смысле, что закурсивленное замечание из решениж упр. 3.4 можно
добавить к этому определению, получив в результате эквивалентное определе-
определение. — Прим. перев.
54
3. Машины Тьюринга
упр. 3.9. Тогда функция t из упр. 3.6 оказалась бы вычислимой
в следующем смысле: чтобы вычислить значение <(п), запустите
машины 5 и М„ в их начальных состояниях, когда они считыва-
считывают самые левые клетки сплошных блоков из п единиц на лентах с
пустыми символами в остальных местах.
Случай 1. Машина Мп никогда не останавливается. Тогда в кон-
конце концов должна остановиться машина S, считывая при этом 1 на
ленте с пустыми символами во всех остальных клетках. В этот мо-
момент мы узнаем, что М„ никогда не остановится, и, следовательно,
будем знать, что соответствующая функция /„ не определена для
значения аргумента п, так что t(n) = 1.
Случай 2. Машина Мп в конце концов останавливается. Но если
это так, то, посмотрев на ленту, можно решить, определено /п(я)
или нет3, и тем самым понять, не определено t(n) или равно едини-
единице. Итак, если проблема самоприменимости разрешима, то функ-
функция t оказывается вычислимой (пусть даже несколько необычным
способом), а потому, согласно тезису Чёрча, t вычислима с помо-
помощью некоторой машины Тьюринга, что противоречит доказанному
в упр. 3.6.
З.Ю(Ь). Если бы проблема остановки была разрешима, т.е. функ-
функция Л была бы вычислимой, то разрешимой оказалась бы и пробле-
проблема самоприменимости, т.е. функция s допускала бы вычисление,
так как s(n) = h(n, n) для каждого натурального п.
,11
3Следует помнить, что, согласно упр. 3.9, значение fn(m) может быть не
определено, даже если машина Мп останавливается, будучи запушенной на
записи числа т: для того чтобы /п('и) было определено, нужно еще, чтобы
заключительная конфигурация удовлетворяла некоторым условиям. — Прим.
персе.
Невычислимость в контексте проблемы^
усердного бобра ;i(' ^m
В этой главе мы демонстрируем еще один пример невычисли-
невычислимой функции путем разработки упр. 3.7 и 3.8; мы показываем, что
проблема усердного бобра неразрешима. В следующей главе мы по-
построим невычислимую функцию t с помощью метода диагонализа-
ции, примененного к нумерации всех функций одной переменной,
вычислимых по Тьюрингу. Невычислимая функция р, построенная
в этой главе, строится более прямым методом.
Мы ограничимся рассмотрением машин Тьюринга, считываю-
считывающих и записывающих всего лишь два символа, В и 1. Можно счи-
считать, что всякая такая машина М следующим образом вычисляет
некоторую (всюду определенную или частичную) функцию / из на-
натуральных чисел в натуральные:
Чтобы вычислить значение (если таковое существует), припи-
приписываемое функцией / значению аргумента п, машина М начина-
начинает работу в состоянии с наименьшим номером, считывая вначале
самую левую в блоке из п единиц на ленте с пустыми символами
во всех остальных клетках. Если в конце концов М останавли-
останавливается в некоторой стандартной конфигурации, т.е. считывая
самую левую в некотором блоке единиц на ленте с пустыми сим-
символами во всех остальных местах, то /(п) есть число единиц в
этом блоке. Если же М никогда не останавливается или остана-
останавливается в нестандартной конфигурации, то /(п) не определе-
определено.
Нетрудно так расширить это определение, чтобы позволить как ар-
аргументам, так и значениям функции / быть любыми натуральными
числами (= неотрицательные целые числа = 0 вместе со всеми по-
положительными целыми числамиI: позволим просто числу единиц в
исходном и финальном блоках быть равными нулю. Таким образом,
1 До этого момента натуральными числами назывались именно положитель-
положительные целые числа, как это и принято в отечественной литературе. Происшедшее
изменение в определении натуральных чисел может привести в дальнейшем к
путанице. В действительно существенных ситуациях будут вноситься необхо-
необходимые уточнения. — Прим. персе.
56 4- Невычислимость в контексте проблемы усердного бобра
если машина М останавливается на некоторой клетке совершенно
пустой ленты, мы полагаем, что /(п) = 0, где г» — число единиц в
исходном блоке. С другой стороны, мы вычислим /@), если запу-
запустим машину М в состоянии с наименьшим номером на совершенно
пустой ленте.
Если машина М вычисляет всюду определенную функцию /, то
мы определяем продуктивность этой машины как /@), а именно
как число единиц на ленте в момент остановки машины М (по-
(поскольку остановка наверняка происходит, и притом в стандартной
конфигурации), запущенной в состоянии с наименьшим номером на
совершенно пустой ленте. Более общим образом, если М вычисляет,
вообще говоря, частичную функцию /, то полагаем
t *ж\ / Д0)> если /@) определено,
продуктивное™ М ) = s п
v ' (^ 0 в противном случае.
Это согласуется с определением из упр. 3.7:
В начальный момент лента пуста, а М находится в состоянии с
наименьшим номером. Если М в конце концов останавливается,
считывая при этом самый левый символ в сплошном блоке еди-
единиц на ленте с пустыми символами во всех остальных клетках,
то ее продуктивностью называется длина этого блока. Если же
М никогда не останавливается или останавливается в нестан-
нестандартной конфигурации, то ее продуктивность считается равной
нулю.
Определим теперь функцию р, как в упр. 3.7: ' ,
р(п) = продуктивность самой продуктивной машины *
с п состояниями.
Проблема усердного бобра (ее формулировка и доказательство не-
неразрешимости даны Радо Тибором в Bell System Tecnical Journal,
May 1962, с. 877-884) есть проблема построения машины Тьюрин- ,
га, вычисляющей функцию р, — причем машины, использующей в
качестве символов только В и 1. Доказательство неразрешимости
этой проблемы опирается на свойства функции р, сформулирован-
сформулированные в упр. 3.7(с) и (d). Цель пп. (а) и (Ь) этого упражнения — дать
читателю освоиться с понятием продуктивности.
Доказательство того, что рA) = 1 (упр. 3.7(а))
Существует бесконечно много различных машин Тьюринга с од-
одним состоянием, использующих в качестве символов только В и 1,
4- Невычислимость в контексте проблемы усердного бобра 57
однако все эти машины распадаются ровно на 25 различных клас-
классов, причем различные машины из одного класса ведут себя совер-
совершенно одинаково: все машины из произвольного фиксированного
класса различаются только именами (q\, или q%, или ... ) своего
единственного состояния. Эти 25 классов соответствуют 25 раз-
различным графам переходов с единственной (безымянной) вершиной,
число стрелок в которых (из этой вершины в нее же) равно 0, или 1,
или 2.
В частности, имеется единственный такой граф переходов без
единой стрелки вообще. Соответствующие ему машины останавли-
останавливаются немедленно на пустой еще ленте, и потому их продуктив-
продуктивность равна нулю.
Машины с одним состоянием и двумя стрелками в графе пере-
переходов, помеченными «В : —» и «1 : —» (где каждый знак — может
быть R, или L, или В, или 1), не останавливаются никогда, и по-
потому продуктивность каждой из них есть 0. Они никогда не оста-
останавливаются, потому что независимо от того, какой символ они
считывают, у них всегда находится инструкция, которой надо сле-
следовать, пусть даже инструкция вида «напечатайте пустой символ
в (пустой) клетке, считываемой вами, и вернитесь в состояние, в
котором находитесь». Таких графов переходов имеется 4 х 4 = 16 в
соответствии с 4 способами, которыми можно заполнить каждый
из пробелов.
Еще имеется 8 графов переходов с одним состоянием и ровно с
одной стрелкой, помеченной «В : —» или «1 : —». Если метка имеет
вид «1 : —», то эта машина останавливается немедленно, поскольку
исходная лента пуста, и, значит, продуктивность машины есть 0; из
четырех графов со стрелкой, помеченной «В : -», три соответству-
соответствуют машинам, не останавливающимся никогда и потому имеющим
продуктивность 0. Таковы графы, единственная стрелка которых
помечена «В : R» или «В : L» (машины-путешественницы) или
«В : В». Единственный оставшийся граф изображен на рис. 4-1.
вл
8
Рис. 4 — 1. Граф-схема машины наибольшей
продуктивности с одним состоянием.
Машины с таким графом печатают одну единицу на изначально
пустой ленте и останавливаются, считывая эту единицу. Поэтому
58 4- Невычислимость в контексте проблемы усердного бобра
эти машины имеют продуктивность 1. Поскольку продуктивность
всех других машин равна 0, заключаем, что продуктивность самой
продуктивной машины с одним состоянием, использующей в каче-
качестве символов только В и 1, равна 1, и мы доказали, что рA) = 1.
Доказательство того, что рD7) > 100 (упр. 3.7(Ь))
Завершая рассмотрение примера 3.3, мы описали машину с
47 состояниями, имеющую продуктивность 100. Не исключается,
конечно, что существуют машины с 47 состояниями, продуктив-
продуктивность которых больше, чем 100, но нами доказано, что продук-
продуктивность самой продуктивной из машин с таким числом состоя-
состояний не менее 100: рD7) > 100. Чтобы получить ясное представление
о том, как выглядит наша машина, введем, как это показано на
рис. 4-2, обозначение для графа переходов машины с 25 состояни-
В Л
Рис. 4-2./@) = 25.
ями, печатающей единицы на пустой ленте и останавливающейся
затем в стандартной конфигурации. Аналогичное (см. рис. 4-3)
обозначение введем для графа переходов машины с 12 состояния-
состояниями из примера 3.2, удваивающей число единиц на ленте. (При этом
нами изменено положение некоторых вершин и удалены пометки
на стрелках.) Теперь машина с 47 состояниями, обладающая про-
продуктивностью 100, получается путем последовательного соедине-
соединения двух экземпляров удваивающей машины и подключением вхо-
входа полученной машины к выходу «напишите 25 единиц»-машины,
где под последовательным соединением понимается отождествление
начальной вершины одной машины с конечной вершиной другой.
Последовательно соединяя приведенные на рис. 4-4 три машины в
указанном порядке, получим машину с рис. 4-5: машину с 47 состо-
состояниями и с продуктивностью 100. Если у вас вызывает недоумение
нумерация состояний, то вы можете представлять себе, что 12 со-
состояний средней, скажем, машины имеют номера 25 + 0, 25 +1, ...,
25 + И, воображая при этом, что последовательные вершины на
рис. 4-3 перенумерованы числами 0, 1, ..., 11 вместо 1, 2, ..., 12.
^4- Невычислимость в контексте проблемы усердного бобра 59
,.;.{¦-. ¦,.м-?;
¦'!'<":
Рис. 4-3. /(п) = 2п.
Удвойте \_ _У Удвойте
+ B5) строчку (Зб) + (зб) строчку D7)
РДиниц
Рис. 4-4. Последовательное соединение трех машин.
' Удвойте уУ Удвойте
^ 25 B5^ строчку C6) строчку D7)
,РДиниц
Рис. 4-5. /@) = 100.
¦:*
Доказательство того, что р(п + 1) > р(п) (упр. 3.7(с))
Возьмем произвольную из наиболее продуктивных машин с
п состояниями и добавим еще одно состояние, как на рис. 4-6.
Результатом этого будет машина сп + 1 состояниями и с продук-
продуктивностью р(п) + 1. Могут, конечно, найтись машины с п + 1 со-
состояниями, обладающие большей, чем эта, продуктивностью, но
мы, во всяком случае, доказали, что продуктивность самой продук-
продуктивной машины сп + 1 состояниями больше (хотя бы на 1), чем
продуктивность самой продуктивной машины с п состояниями.
60 4- Невычислимость в контексте проблемы усердного бобра
Машина наибольшей продуктивности ;
с п состояниями
V.L
В Л
Рис. 4-6. /@) = p(n) + 1.
Доказательство того, что р(п + 11) > 2п (упр. 3.7(d))
В примере 3.3 мы построили машину с г» + 11 состояниями и с
продуктивностью 2п; ее схема приведена на рис. 4-7. Поскольку
Рис. 4-7./@) = 2п.
вполне могут найтись машины с п+11 состояниями, обладаю-
обладающие большей продуктивностью, мы не можем утверждать, что
р(п + 11) = 2п; можно лишь утверждать, что р(п + 11) больше «ли
равно 2п.
Доказательство неразрешимости проблемы
усердного бобра (упр. 3.8)
Доказательство проводится от противного; мы выведем проти-
противоречие (а именно, что 0 > 1) из предположения о разрешимости
проблемы усердного бобра. Наше предположение состоит в том,
что существует машина Тьюринга (назовем ее В В) с к, напри-
например, состояниями, вычисляющая функцию р. Эта машина должна
считывать и записывать только символы В и 1. Будучи запущенной
в состоянии 1 на самой левой клетке сплошного блока из п единиц
на ленте с пустыми символами во всех остальных клетках, она в
конце концов останавливается в состоянии2 к на самой левой клетке
сплошного блока из р(п) единиц на ленте с пустыми символами во
всех остальных клетках.
2 До этого момента в определении вычисления на машине Тьюринга требо-
требование остановки в фиксированном состоянии отсутствовало. В то же время
ясно, что это требование не является существенным и не уменьшает класс
вычислимых функций. — Прим. персе.
4- Невычислимость в контексте проблемы усердного бобра 61
Для начала заметим, что если существует такая машина,
Жак ВВ, то существует некоторая машина с п + 2к состояниями,
щмеющая продуктивность р(р(п)); см. рис. 4-8. Таким образом,
Рис.4-8.
= р(р(п)).
если ВВ существует, то продуктивность самой продуктивной ма-
машины с п + 2к состояниями должна быть не менее р(р(п)):
р(п + 2к) > р(р(п)), если ВВ существует.
A)
При этом, существует ВВ или нет, мы знаем, чтор(п+1) > р(п)
для всякого натурального п, откуда следует, что для любых нату-
натуральных t и j
Р(») > P(j), если i > j. B)
Отметим, что отрицания утверждений p(t) > p(j) и i > j имеют
вид p(j) > p(i) и j > i соответственно: если неверно, что первое чи-
число больше второго, то второе больше или равно первому. Поэтому
обращением B) получаем
если p(j) > p(i), то j > t
C)
для всех натуральных i и j. Теперь из C) и A), подставляя
j = п + 2к и г = р(п), получим:
если ВВ существует, то п + 2к> р(п)
D)
для всякого натурального п.
Будучи верным для произвольного п, D) остается верным и при
увеличении п на 11:
если В В существует, то п+ 11 + 2к>р(п+ 11). E)
Но мы уже доказали (упр. 3.7(d)), что
р(п+11)>2п, F)
62 4- Невычислимость в контексте проблемы усердного бобра
существует ВВ или нет. Из неравенств E) и F) вытекает, что для
всех натуральных п,
если В В существует, то п + 11 + 2к > 2п. G)
Вычитая из обеих частей неравенства G) по п, получим:
если ВВ существует, то 11 + 1к > п (8)
для всякого натурального п. В частности, при п = 12 + 2fc полу-
получаем ll + 2ife>12 + 2Jfc, или, вычитая по 11 + 2* из обеих частей
неравенства,
0>1, если В В существует. (9)
Таким образом, предположение о существовании ВВ приводит нас
к обещанному противоречию.
Значит, функция р не допускает стандартного вычисления на
машине Тьюринга, определенного в начале этой главы. Чтобы вы-
вывести отсюда заключение о невычислимости функции р в самом
общем смысле, мы должны согласиться, что если некоторая функ-
функция вычислима вообще, то она допускает и стандартное вычисление
на некоторой машине Тьюринга. Соответствующее соглашение (од-
(одна из возможных форм тезиса Чёрча) таково:
Если всюду определенная функция / вычислима в интуитив-
интуитивном смысле, то существует машина Тьюринга, использующая в
качестве символов только В и 1, которая, будучи запущенной в
состоянии с наименьшим номером на самой левой клетке сплош-
сплошного блока из п единиц на ленте с пустыми символами во всех
остальных клетках, в конце концов останавливается на самой ле-
левой клетке сплошного блока из /(п) единиц на ленте с пустыми
символами во всех остальных клетках.
(Несущественно, принимаем мы этот тезис для произвольных
натуральных чисел или же ограничиваемся лишь положительны-
положительными целыми.) Не обладая точной общей формулировкой понятия вы-
вычислимости, мы не можем доказать этот тезис; мы можем лишь
убедиться в его правдоподобии в результате исследований, подоб-
подобных тем, что проведены нами в гл. 6-8.
В заключение посмотрим на функцию р еще раз в свете тези-
тезиса Чёрча. Поставим вопрос: «Почему функция р не вычислима в
каком-либо интуитивном смысле?». Прежде всего заметим, что су-
существует лишь конечное число различных графов переходов машин
4. Невычислимость в контексте проблемы усердного бобра 63
с п состояниями; мы считаем при этом различными, в частности,
графы, различающиеся только начальным состоянием 1 (нумера-
(нумерация остальных состояний несущественна). Поэтому для каждого п
мы можем (воображаемым образом) одновременно запустить все
машины с п состояниями в начальном состоянии 1 на пустой ленте
и ждать, что произойдет. Время от времени то одна, то другая ма-
машина будут останавливаться, и мы сможем проверить, останавли-
останавливаются ли они на самых левых клетках сплошных блоков из единиц
на лентах с пустыми символами во всех остальных клетках. Бели
машина останавливается в стандартной конфигурации, то мы опре-
определим ее продуктивность, подсчитав число единиц в окончательном
блоке. Если же она останавливается в нестандартной позиции, мы
знаем, что ее продуктивность равна нулю. Однако здесь есть зацеп-
зацепка: некоторые из запущенных машин могут не остановиться вовсе,
так что, сколько бы времени мы ни ждали, не будет возможно-
возможности определить их продуктивность описанным выше способом. Эти
машины имеют нулевую продуктивность именно потому, что они
никогда не останавливаются.
Зевс, работая все быстрее и быстрее, как это показано в
табл. 2-2, мог бы промоделировать все шаги бесконечного вычи-
вычисления за 1 секунду, или за полсекунды, или даже за четверть ... —
как он пожелает. Поэтому он в состоянии промоделировать беско-
бесконечно много вычислений, индивидуально конечных или бесконеч-
бесконечных, неважно, — и все это за 1 секунду: он потратит полсекунды
на первое вычисление, четверть секунды на второе и т.д. Для Зевса
бесконечная, без остановки работа машины не была бы препятстви-
препятствием: он мог бы вычислять функцию р.
Мы же, однако, как и наши машины, за конечный промежуток
времени, каким бы долгим он ни был, в состоянии выполнить лишь
конечное число операций. Любая систематическая процедура, по-
позволяющая проверять, останавливается ли то или иное вычисление,
была бы приемлема для нас только в том случае, если бы она приво-
приводила к результату за то или иное конечное число шагов независимо
от того, к какой машине ее применяют. Если бы мы располагали
такой процедурой, мы применили бы ее к графам машин с п состо-
состояниями (в то время как они бы работали, запущенные в начальных
состояниях на пустых лентах). Через некоторый конечный проме-
промежуток времени каждая из машин либо остановилась бы, либо про
нее стало бы известно, что она не остановится. Таким образом, для
каждого т» существовал бы конечный промежуток, спустя который
64 4- Невычислимость в контексте проблемы усердного бобра
мы знали бы продуктивность любой из машин с п состояниями. Но
тогда для каждого п мы могли бы вычислить р(п): функция р оказа-
лась бы вычислимой в интуитивном смысле, если бы существовал
алгоритм определения неостанавливающихся вычислений — про-
процедура, обязательно заканчивающаяся через то или иное конечное
число шагов независимо от того, к какой из неостанавливающихся
машин ее применяют.
Проблема остановки — это проблема построения систематиче-
систематического метода — эффективной процедуры — для выявления машин
Тьюринга, которые, будучи запущенными в начальном состоянии
на пустой ленте, никогда не остановятся. Мы видели, что если бы
проблема остановки была разрешимой, то функция р оказалась бы
вычислимой в интуитивном смысле. Но мы убедились, что функ-
функция р не допускает стандартного вычисления ни на какой машине
Тьюринга. Вывод:
Если тезис Чёрча верен, то проблема остановки неразрешима.
Позднее (в гл. 10) мы воспользуемся этим обстоятельством, чтобы
доказать, что в предположении истинности тезиса Чёрча проблема
разрешения логики первого порядка неразрешима.
Вопрос. Почему три машины на рис. 4 - 8 в отличие от того, как
это сделано на рис. 4-4 и 4-5, соединены не обычным последова-
последовательным способом? (Ответ см. ниже.)
Ответ. Разберемся вначале, почему в случае рис. 4-4 и 4-5 воз-
возможно простое соединение. Отождествление заключительного со-
состояния машины «Напишите 25 единиц» с начальным состоянием
удваивающей машины возможно, поскольку эти состояния имеют
вид
1-.L
25)
ВЛ
Их отождествление не приводит к противоречиям в инструкциях,
касающихся поведения машин в состоянии 25:
V.L
4. Невычислимость в контексте проблемы усердного бобра 65
Аналогичная ситуация имеет место для заключительного состояния
первой удваивающей и начального состояния второй удваивающей
машин:
0:Я
Но у нас нет никаких гарантий, что машина ВВ не имеет ин-
инструкции, определяющей, что она должна делать, считывая пустой
символ. (Заметим, что начальное состояние вполне может иметь и
другие функции: машина может возвращаться в него на дальней-
дальнейших этапах своей работы, если, как это имеет место с машиной
умножения из упр. 3.4, оно входит в состав замкнутых петель.)
Итак, из сказанного следует, что заключительное состояние маши-
машины «Напишите п единиц» и начальное состояние машины ВВ могут
оказаться несогласованными, как, например, состояния
V.L
v.R
ВЛ
B-.L
Если отождествить эти состояния, то машина будет иметь проти-
противоречивые инструкции по поводу того, что ей делать в состоянии п
(= п + 1), если она считывает пустой символ. ;
у*
t
Неразрешимость в контексте
диагонализации - >Z
.,,1
В этой главе мы демонстрируем различные невычислимые
функции, подобные рассмотренным в упр. 3.8, 3.9 и 3.10. Мы на-
называем эти функции просто «невычислимыми», а не «не допуска-
допускающими вычисление на машинах Тьюринга», имея в виду тезис
Чёрча, несомненность которого обосновывается в гл. 6-8. Всюду
в этой главе термин «функция» обозначает функцию на множестве
положительных целых чисел со значениями в том же множестве.
Существование невычислимых функций как таковое доказыва-
доказывается легко и просто, поскольку нам известно (упр. 2.4(d)), что мно-
множество всех машин Тьюринга (задаваемых конечными наборами
четверок) счетно, тогда как (упр. 2.3) множество всех функций не-
несчетно. Если бы множество всех функций, вычислимых по Тьюрин-
Тьюрингу, совпадало с множеством всех функций вообще, то это множество
должно было бы одновременно быть и не быть счетным. Следо-
Следовательно, эти два множества различны: первое есть собственное
подмножество второго.
Приведенное доказательство является довольно грубым и эс-
эскизным, поскольку оно не опирается на точное определение тью-
ринговской вычислимости функций из множества положительных
целых чисел в него же. Машины Тьюринга работают с символа-
символами, а не с числами. Прежде чем говорить о тыоринговском вы-
вычислении числовых функций, мы должны зафиксировать способ,
которым числовые значения аргумента и функции представляют-
представляются на машинной ленте, например, как это было сделано для сум-
суммирующей и умножающей машин из упр. 3.4 и 3.5. Выбранный
нами способ изображения чисел с помощью конечных последова-
последовательностей из единиц особенно прост, но это не существенно: с
тем же успехом можно было использовать десятичную или лю-
любую другую систему записи. Что существенно, так это то, что
такие детали, как система счисления, должны быть фиксирова-
фиксированы тем или иным образом. Наши соглашения по этой части та-
таковы.
5. Неразрешимость в контексте диагонализации 67
(a) Значения аргументов функции изображаются блоками еди-
единиц, между которыми помещается по одному пробелу; остальная
часть ленты остается при этом пустой. Таким образом, перед вы-
вычислением, скажем, суммы 3 + 2 лента имеет вид 111511.
(b) В начальный момент машина считывает самую левую из
имеющихся на ленте единиц. Таким образом, если начальное со-
состояние машины есть 1, то начальная конфигурация при вычисле-
вычислении 3 + 2 такова: 111511.
(c) Если подлежащая вычислению функция определена для на-
набора значений аргументов, представленного в начальный момент
на ленте, то машина спустя некоторое время останавливается в
стандартной заключительной конфигурации, т.е. считывая самую
левую единицу в их блоке, записанном на ленте с пустыми симво-
символами во всех остальных клетках. Количество единиц в этом блоке
и есть значение функции для данного набора значений аргумен-
аргументов. Так, заключительная конфигурация при вычислении 3 + 2 с
помощью суммирующей машины из упр. 3.4 имеет вид 11111.
(d) Если, напротив, для данного набора значений аргументов
функция не определена, то не происходит остановки в стандартной
конфигурации: или машина продолжает безостановочно работать,
или в конце концов останавливается, но в нестандартной конфигу-
конфигурации вроде 5111, или 151, или 111 и т.д.
Начальные конфигурации, описанные выше в пп. (а) и (Ь), будем
называть стандартными начальными конфигурациями, равно как
заключительные конфигурации, описанные в п. (с), будем называть
стандартными заключительными конфигурациями.
После принятия этих уточнений можно считать, что всякая ма-
машина Тьюринга вычисляет некоторую функцию одной переменной,
некоторую функцию двух переменных и, вообще, некоторую функ-
функцию п переменных, каково бы ни было положительное целое п. Рас-
Рассмотрим, например, машину, задаваемую единственной четверкой
gill?2 с начальным состоянием qi. Будучи запущенной в стандарт-
стандартной начальной конфигурации, она немедленно остановится, оставив
при этом ленту без изменений. Если на ленте первоначально имел-
имелся только один блок единиц, то и заключительная конфигурация
машины будет стандартной, и машина, таким образом, вычисляет
тождественную функцию i одной переменной »(n) = n для всякого
положительного целого п. Итак, наша машина вычисляет некото-
некоторую всюду определенную функцию одной переменной. Однако если
68
5. Неразрешимость в контексте диагонализации
в начальный момент на ленте имеется два или более блоков единиц,
то заключительная конфигурация не будет стандартной. Следова-
Следовательно, эта машина вычисляет «самую частичную» функцию двух
переменных, а именно функцию, не определенную ни для одной па-
пары значений аргументов. Аналогично и для произвольного числа п
аргументов (п > 2) эта машина вычисляет нигде не определенную
функцию.
С другой стороны, машина, изображенная на рис. 5-1, прВ вся-
-щ
*'
B-.R
Рис. 5-1. /(*!,...,Х„) = 1.
ком п вычисляет всюду определенную функцию, приписывающую
одно и то же значение, а именно 1, любому n-набору аргументов.
Будучи запущенной в состоянии 1 в стандартной начальной конфи-
конфигурации, эта машина (перемещаясь по циклу из состояний 1 и 2)
стирает первый блок единиц и переходит в состояние 3, считывая
при этом вторую клетку справа от первого блока. Если она видит
там пустой символ, то понимает, что стерла на ленте все, а потому
печатает одну единицу и останавливается в состоянии 4 в стан- ,
дартной заключительной конфигурации. Если же она обнаружива-
обнаруживает там 1, то вновь попадает в цикл из состояний 1 и 2, уничтожает
второй блок единиц и, снова перейдя в состояние 3, выясняет, опу-
опустела уже лента или на ней сохранились блоки, с которыми машине
еще предстоит разбираться.
В этой главе мы будем иметь дело с функциями одной перемен-
переменной. Мы покажем, что множество всех таких функций не допускает
перечисления, в то время как множество всех функций одной пере-
переменной, вычислимых на машинах Тьюринга, может быть зануме-
занумеровано. После этого, детально рассмотрев их нумерацию, мы по-
построим некоторую конкретную функцию t одной переменной, кото-
которая не вычисляется никакой машиной Тьюринга. Согласно нашим
договоренностям, машина М вычисляет функцию / одной перемен-
переменной тогда и только тогда, когда для каждого п = 1, 2, 3, ..., для
5. Неразрешимость в контексте диагонализации
69
которого /(п) определено (и ни для каких других п), машина М,
будучи запущенной в стандартной конфигурации с п единицами на
ленте, в конце концов останавливается в стандартной же конфи-
конфигурации с /(п) единицами на ленте. Функция / называется вычи-
вычислимое по Тьюрингу тогда и только тогда, когда она вычисляется
некоторой машиной М в соответствии с этим определением.
Мы перечисляем функции одной переменной, вычислимые по
Тьюрингу, с помощью нумерации машин Тьюринга. В свою оче-
очередь мы задаем каждую машину Тьюринга, выписывая в виде еди-
единой строчки все определяющие машину четверки; между соседними
четверками мы не делаем пробелов, а первой помещаем четверку,
первым символом которой является начальное состояние машины.
Пример: изображенная на рис. 5-1 машина с начальным состояни-
состоянием gi задается строчкой
Понятно, что каждая машина Тьюринга задается таким способом с
помощью некоторой конечной строчки букв из счетно бесконечного
алфавита
t R, L, So, q\, Si, ?2. S2, 93, S3, ... . A)
He каждое слово в этом алфавите задает какую-либо машину Тью-
Тьюринга. Такое слово задает некоторую машину Тьюринга в точности
тогда, когда оно удовлетворяет следующим условиям:
(a) Его длина делится на 4.
(b) На позициях с номерами
1, 4, 5, 8, 9, 12, ..., An, 4n+l, ...
встречаются только символы qi, q%, Чз> • • • •
(c) На позициях с номерами 2, 6, 10, ..., 4п + 2, ...
встречаются только символы So, Si, S2, ¦•¦ •
(d) На позициях с номерами 3, 7, 11, ..., 4п + 3, ...
встречаются только символы R, L, So, Si, ....
(e) Никакая конфигурация вида qiSj
не встречается в слове более одного раза.
Условие (е) не является единственно возможным. Его цель — ис-
исключить взаимно противоречащие инструкции; однако той же цели
можно добиться и другим способом, допускающим повторяющиеся
четверки: если конфигурация вида qiSj встречается в слове более
B)
70
5. Неразрешимость в контексте диагонализации
одного раза, то при каждом ее вхождении за ней должна стоять
одна и та же пара символов.
Из упр. 2.4(d) мы знаем, что множество всех слов в счетно бес-
бесконечном алфавите A) является счетным: образно говоря, их можно
расположить в виде единого (хотя, возможно, содержащего пробе-
пробелы) списка u>i, югi и>з, Если из этого списка удалить слова,
не задающие машины Тьюринга, то получится другой список (с
пробелами), в котором каждая машина Тьюринга названа хотя бы
однажды и ничего более не упомянуто. Теперь (все еще образно
говоря) давайте закроем пробелы, чтобы получить сплошной, без
пробелов, список Mi, M2, М3, . ¦. всех машин Тьюринга. Посколь-
Поскольку всякая машина Тьюринга определяет некоторую определенную
функцию из натуральных чисел в натуральные, последний список
машин определяет список
Л, Л, /з, •••?, C)
всех вычислимых по Тьюрингу функций одной переменной, где для
каждого п через /п обозначена всюду определенная или частичная
функция одной переменной, вычисляемая машиной М„.
Итак, как только мы определим некоторую нумерацию wi, w2,
и>з, .. .слов в алфавите A), мы автоматически получаем некоторую
нумерацию C) всех вычислимых по Тьюрингу функций одной пе-
переменной. Занумеруем теперь эти слова по методу, описанному в
конце гл. 21. Мы получим (содержащий пробелы) список, первое
место в котором занимает слово w\2, а именно R. Вообще, номер
произвольного слова в этом списке задается (в десятичной запи-
записи) строчкой, получающейся из этого слова путем замены каждого
вхождения буквы R на 12, буквы L — на 122, буквы So — на 1222
и т.д.: п-я буква алфавита A) заменяется единицей, за которой сле-
следует п двоек.
Процесс получения нумерации машин из нумерации слов явля-
является тривиальным (хотя и трудоемким). Первое из слов, определя-
определяющее машину Тьюринга (т.е. удовлетворяющее условиям B)), —
это qiSoRqi- Оно есть wn при п = 1222212221212222 — квадрильон
«с довеском». Машина М\ показана на рис. 5-2(а). В любой стан-
стандартной начальной конфигурации она считывает символ 1, а пото-
потому останавливается мгновенно в своем начальном положении. Та-
Таким образом, /i есть »', тождественная функция, т.е. /i(n) = п для
1 Имеется в виду решение упр. 2.4(d). — Прим. переа.
5. Неразрешимость в контексте диагоналиэацчж
B.R . B.L
71
...... ¦ Рис. 5-2.
всякого п. Функция /г совпадает с /i, поскольку второе из слов,
задающих машины Тьюринга, есть qiSoLqi, являющееся wn при
п = 12222122212212222. Машина М2 изображена на рис. 5-2(Ь).
Она тоже немедленно останавливается в стандартной заключитель-
заключительной конфигурации, если ее запустить в стандартной начальной кон-
конфигурации с единственным блоком единиц на ленте.
Итак, мы занумеровали вычислимые по Тьюрингу функции од-
одной переменной путем нумерации машин, их вычисляющих. Су-
Существование такой нумерации имеет следствием существование
невычислимых функций одной переменной. Как только такая ну-
нумерация оказывается точно определенной, немедленно возникает
возможность предъявить конкретную невычислимую функцию, а
именно функцию и, определяемую следующим образом (см. упр. 2.3
и З.б):
если fn(n) не определено,
(п) + 1 в противном случае.
D)
Очевидно, что и — настоящая всюду определенная функция одной
переменной, однако она невычислима по Тьюрингу, т.е. и не совпа-
совпадает ни с /i, ни с /г, ни с /з и т.д. Доказательство. Предположим,
что а — одна из функций, вычислимых по Тьюрингу, имеющая,
например, номер т. Тогда для всякого натурального п либо и(п) и
*/m(n) оба определены и равны, либо не определено ни одно из этих
значений. Рассмотрим теперь случай п = m:
и(т) = fm(m)
-I1'
если fm(m) не определено,
(т) + 1 в противном случае.
E)
Тогда вне зависимости от того, определена функция /т для значе-
значения аргумента т или нет, мы все равно приходим к противоречию:
либо /т(тп) не определено, и тогда E) говорит нам, что оно имеет
72
5. Неразрешимость в контексте диагонализации
значение 1 (и оказывается одновременно определенным и не опреде-
определенным), либо fm(m) определено и оказывается равным fm(™) + 1
(откуда выводится, что 0 = 1). Поскольку противоречие возникло
из предположения, что « присутствует где-то в списке /i, /2, ...,
/m, ..., заключаем, что это предположение ложно, а потому функ-
функция и невычислима по Тьюрингу.
Хотя функция и и не может быть вычислена ни на какой машине
Тьюринга, мы в состоянии легко вычислить несколько ее первых
значений. Так, поскольку Д = /2 = t — тождественная функция,
мы имеем ДA) = 1 и /2B) = 2, так что, согласно D), получаем
«A) = 2 и иB) = 3. Отметим, что нет никакого противоречия ни
в сказанном, ни в определении D) функции и. Соотношение же E)
содержит противоречие лишь из-за соединения D) с предположени-
предположением о том, что функция и вычислима по Тьюрингу, т.е. вычисляется
машиной Мт при некотором натуральном т. Содержащееся в E)
противоречие опровергает это предположение, но никоим образом
не отменяет определение D).
Теперь может показаться, что мы в действительности могли бы
вычислить и(п) для любого натурального п — лишь бы это позво-
позволяли наши запасы времени. В самом деле, мы только что нашли
иA) и «B), и может показаться, что и для дальнейших значений
аргумента это можно делать тем же стандартным способом, лишь
бы позволило время. Вопрос, однако, заключается в том, насколько
необходимо вмешательство случая или нашей особенной изобрета-
изобретательности для того, чтобы вычисление значений функции и стало
возможным. Может показаться, что в этом нет нужды, поскольку
напрямую определяется, какими четверками задаются машины М„
для п = 1, 2, 3, .... (Это делается напрямую, но оказывается не-
невозможным ни для какого человека, так как время, необходимое для
выполнения тривиальных вычислений, превышает при больших п
пределы человеческой жизни, а по всей вероятности, и время суще-
существования и рода людского.) Но важнейший вопрос состоит в том,
окончит ли хоть когда-нибудь машина Мп свои вычисления, буду-
будучи запущенной в некоторой стандартной начальной конфигурации и
переработав ее в соответствующую стандартную заключительную
конфигурацию. Является ли стандартным решение этой задачи?
Если да, то функция и, несмотря ни на что, оказывается вычисли-
вычислимой — пусть даже она не вычисляется никакой машиной Тьюринга.
Но является ли стандартным решение вопроса о том, остано-
остановится в конце концов машина Тьюринга (причем в стандартном
5. Неразрешимость в контексте диагонализации
73
положении) или нет? Конечно, можно совершенно механически про-
прослеживать последовательность действий машины М„ после того,
как определена ее начальная конфигурация, и, если Мп в конце
концов останавливается, мы рано или поздно получим информа-
информацию об этом путем отслеживания машинных операций. Но как
быть, если машине М„ при данной начальной конфигурации не
суждено остановиться? Можно ли в механическом процессе про-
прослеживания ее операций указать момент, когда становится ясно,
что она не остановится никогда? В простейших случаях это, ко-
конечно, так — например, очевидно, что четверка qiSiSiqi задает
машину, которая, будучи запущенной на клетке, содержащей 1, не
остановится никогда. Столь же очевидно, что никогда не остано-
остановится машина, задаваемая строчкой qiSiSoqiqiSoLqi. Но если мы
рассматриваем более сложные случаи, то существование стандарт-
стандартной, механической процедуры, позволяющей решать, остановится
ли хоть когда-нибудь данная машина, если ее запустить в данной
конфигурации, никоим образом не очевидно. Рассмотрим, напри-
например, умножающую машину из упр. 3.4. Она описывается различны-
различными строчками из 124 символов в алфавите (IJ. Вообразим, что мы
встретились с одной из таких строчек в списке w\, W2, Конеч-
Конечно, проверка того, описывает ли данная строчка некоторую машину
Тьюринга, является стандартной. Довольно несложно построить по
такой строчке и граф переходов машины, подобный изображенному
в гл. 3, — но без аннотации и без сопровождающего текста, объяс-
объясняющего устройство и работу процедуры чехарды и все остальное.
Существует ли стандартный, механический метод, который позво-
позволил бы в этом и в более сложных случаях определять, остановится
ли в конце концов в некоторой стандартной заключительной конфи-
конфигурации машина, запущенная в данной начальной конфигурации?
Если это так, то функция и вычислима, хотя машины Тьюринга
ее не вычисляют. Но если это не так, то наша попытка усмотреть
в и функцию, вычислимую некоторым, хотя и не тьюринговским
способом, терпит неудачу.
Итак, ключевой оказывается проблема построения некоторого
универсального метода, который бы по данному описанию маши-
машины Тьюринга и по произвольной начальной конфигурации ленты
за конечное число шагов определял бы, остановится ли в конце
Одна машина Тьюринга может иметь несколько различных описаний, по-
поскольку четверки, ее задающие, можно записывать в строчку-описание в про-
произвольном порядке.— Прим. персе.
74
5. Неразрешимость в контексте диагонализации
концов наша машина, да еще в стандартной конфигурации, если
ее запустить в данной начальной конфигурации. Бели такой ме-
метод существует, то тьюрингово понятие вычислимости оказывает-
оказывается слишком узким: в этом случае существуют вычислимые функ-
функции, не являющиеся вычислимыми по Тьюрингу, и, в частности,
такова функция и. Если же тьюрингово понятие вычислимости до-
достаточно широко, чтобы охватить все функции, вычислимые хоть
в каком-либо интуитивном смысле, то сформулированная проблема
оказывается неразрешимой.
Еще одна родственная проблема, подобным же образом оказы-
оказывающаяся неразрешимой, если только тьюрингово понятие вычи-
вычислимости универсально, — это проблема остановки из упр. 3.10:
построить эффективный метод, позволяющий определить, остана-
останавливается ли хоть когда-нибудь произвольная данная машина Тью-
Тьюринга (неважно, в стандартной или в какой-либо иной заключитель-
заключительной конфигурации), если ее запустить в начальном ее состоянии
считывающей самую левую клетку в сплошном массиве единиц на
ленте с пустыми символами во всех остальных клетках. Замеча-
Замечательно, что независимо от того, принимается тезис Чёрча или нет,
следующая функция Л, вычислимость которой в интуитивном смы-
смысле эквивалентна разрешимости проблемы остановки, оказывается,
как можно доказать, невычислимой по Тьюрингу: Л(тп, п) = 2 или 1
в соответствии с тем, остановится в конце концов или нет машина
Тьюринга с номером т, если ее запустить в начальном состоянии
считывающей самую левую единицу в сплошном блоке из п еди-
единиц на ленте с пустыми символами во всех остальных клетках.
Таким образом, если тезис Чёрча верен, то проблема остановки
неразрешима.
Доказательство невычислимости по Тьюрингу функции /», при-
приводимое нами здесь, является более прямым, чем доказательство,
данное при решении упр. 3.10: на этот раз мы не выводим невычи-
невычислимость h из невычислимости функции и, а доказываем ее прямо,
с помощью диагональных рассуждений. С этой целью мы определя-
определяем h полностью, получая всюду определенную функцию, в то время
как в упр. 3.10 задавались лишь условия, при которых h принимает
значение 1. Доказательство проводится от противного: мы пока-
покажем, что если Л вычисляется некоторой машиной Тьюринга Я, то
должна существовать другая машина Тьюринга Мт, такая, что
для любого натурального п машина Мт останавливается тогда
и только тогда, когда машина Мп не останавливается, если обе
5. Неразрешимость в контексте диагонализации
75
их запустить в их начальных состояниях в самых левых клетках
сплошных массивов из п единиц. Но, конечно же, такой машины Мт
не может быть на свете, так как, если бы она существовала, она,
будучи запущенной в ее начальном состоянии на самой левой клет-
клетке сплошного блока из т единиц на ленте с пустыми символами во
всех остальных клетках, должна была бы остановиться в точности
тогда, когда ее работа при этих начальных условиях продолжалась
бы бесконечно.
Истинность утверждения о том, что если функция Л вычисляет-
вычисляется некоторой машиной Тьюринга Я, то существует описанная выше
машина Тьюринга Мт, можно усмотреть из рис. 5-3. Блок Я
Скопируйте начальный блок из п единиц,
оставив перед копией символ В
Остановитесь
W в точности тогда,
когда h(n, n) = 1
Рис. 5-3. Граф машины Мт.
на рис. 5-3 изображает граф переходов машины Я. Самая ле-
левая вершина изображает начальное состояние машины. Поскольку
функция Л всюду определена, в графе машины Я должна суще-
существовать хотя бы одна вершина, из которой не исходит стрелки,
помеченной (перед двоеточием) единицей. Все состояния, в кото-
которых Я может остановиться, представлены именно такими верши-
вершинами. (Однако некоторым таким вершинам могут соответствовать
состояния, в которых Я не останавливается, поскольку, вычисляя
значение функции Л, она может в этих состояниях никогда не на-
наткнуться на единицу.) Предположим для определенности, что таких
состояний имеется ровно два, и изобразим их вершинами на пра-
правой стороне блока Я. Все остальные вершины и стрелки графа Я
считаются спрятанными внутри блока.
Таким образом, рис. 5-3 изображает граф переходов маши-
машины Мт, содержащей в качестве своей части машину Я. Если ма-
машину Мп запустить в ее начальном состоянии (т.е. в самой левой
вершине) считывающей самую левую клетку в блоке из п единиц
76
5. Неразрешимость в контексте диагонализации
на ленте с пустыми символами во всех остальных клетках, то она
первым делом скопирует данный блок единиц через один пробел на-
направо и затем запустит машину Н обрабатывать эту пару блоков.
Бели машина Н заканчивает свою работу, то вся машина оста-
останавливается тогда и только тогда, когда Н оставляет на ленте
ровно одну единицу. (В момент остановки машины Н на ленте все-
всегда бывают записаны одна или две единицы подряд, а в остальных
клетках стоят пустые символы.)
Таким образом, машина Мт останавливается тогда и только то-
тогда, когда машина Мп не делает этого (т.е. в точности тогда, когда
Л(п, п) = 1), если обе их запустить в их начальных состояниях счи-
считывающими самую левую клетку сплошного блока из п единиц на
ленте с пустыми символами во всех остальных клетках. Подставляя
т = п, мы убеждаемся, что существование машины Мт невозмож-
невозможно, а потому не существует и машины Н: функция h невычислима
по Тьюрингу независимо от того, справедлив тезис Чёрча или нет.
Иными словами, проблема остановки не допускает решения с по-
помощью машины Тьюринга. Если же принять тезис Чёрча, то она
неразрешима и в абсолютном смысле.
Упражнения
5.1. Что представляют собой функции одной и трех переменных,
вычисляемые суммирующей машиной из упр. 3.5?
5.2. Постройте машины Мз и М\ и вычислите значения
иC) и иD). •'*
5.3. Определим функцию t следующим образом: ?
4 ' ^ не
не определено,
если fn(n) не определено,
если fn(n) определено.
Докажите (без помощи тезиса Чёрча), что< не является вычислимой
по Тьюрингу.
5.4. Положим f(m, п) = /m(n) для любых т, п = 1, 2, ... . Вы-
Вычислима ли функция /?
Решения
5.1. Суммирующая машина из упр. 3.5 вычисляет тождествен-
тождественную функцию одной переменной, а функция трех переменных, вы-
вычисляемая ею, — это нигде не определенная функция, не приписы-
приписывающая значения ни одной тройке натуральных чисел.
5. Неразрешимость в контексте диагонализации
77
5.2. Машина Мз задается четверкой qiSoRq2, a M* — четверкой
i. Обе машины вычисляют тождественную функцию одной
переменной, так что «C) = 4, а иD) = 5.
5.3. Бели бы функция t вычислялась, скажем, машиной Тьюрин-
Тьюринга Мк из нашей нумерации, то мы имели бы
1, если /t(Jfc) не определено,
не определено, если /t(ifc) определено.
Но тогда предположение о вычислимости функции t по Тьюрингу
ведет к противоречию (без использования тезиса Чёрча) и потому
является ложным.
5.4. Да. (Воспользуйтесь тезисом Чёрча.)
\. а." /'
Л"
r ' >
.>',•>>. ^1 -„ ¦,'¦*«• Г <г*1
- ' ' ' ^ , J Д/
6. Функции, вычислимые на абаке
79
6
Функции, вычислимые на
вычислимы по Тьюрингу
Трактуемый в широком смысле, тезис Чёрча утверждает, что
всякая механическая процедура, манипулирующая с символами,
в действительности может быть выполнена той или иной маши-
машиной Тьюринга. Так, умножение натуральных чисел, которое мы
склонны представлять себе как механическую процедуру, развер-
развертывающуюся в двух измерениях (умножение «в столбик»), может
быть выполнено на одномерной ленте некоторой машины Тьюрин-
Тьюринга, считывающей и записывающей десять цифр, пробел и, воз-
возможно, некоторое количество вспомогательных символов, исполь-
используемых ею в процессе вычисления в целях учета промежуточных
результатов, но не присутствующих на ленте ни в начале вычи-
вычислений, ни после остановки машины. Однако в упр. 3.4 мы виде-
видели, как эту манипуляцию можно осуществить и на машине Тью-
Тьюринга, удовлетворяющей следующим дополнительным требовани-
требованиям.
A) Два перемножаемых числа изображаются блоками из еди-
единиц, разделенными единственным пробелом, на ленте с пустыми
символами во всех остальных клетках, а результат, остающийся на
ленте после остановки машины, изображается единственным бло-
блоком из единиц на ленте с пустыми символами во всех остальных
клетках.
B) Машина начинает работу и заканчивает ее только в стан-
стандартной позиции, т.е. считывая самую левую единицу на ленте.
C) На протяжении всего процесса вычислений машина никогда
не уходит больше чем на две клетки влево от самой левой из единиц,
находившихся на ленте изначально. Таким образом, лента должна
быть бесконечной лишь в одном направлении, а именно вправо.
D) Машина не использует для записи на ленте никаких симво-
символов, кроме В и 1, т.е. задающие машину четверки являются словами
в алфавите
R, L, В, 1, 3i, ?2, 9з, ¦•• •
Будем отныне употреблять термин «вычислимые по Тьюрингу»
применительно к функциям, вычисляющимся на машинах Тьюрин-
Тьюринга в соответствии с этими четырьмя требованиями, а также при
дополнительном условии E), что самая левая в блоке единиц, пред-
представляющем значение функции, появляется в той самой клетке лен-
ленты, в которой и в начальный момент находилась самая левая едини-
единица. Очевидность тезиса Чёрча, принимаемая нами в этой и в двух
следующих главах, позволяет обозреть класс вычислимых по Тью-
Тьюрингу функций в целом: мы убеждаемся, что они объемлют некий
замечательно широкий класс, включающий в себя, по-видимому,
все функции из натуральных чисел в натуральные, допускающие
эффективное вычисление в каком бы то ни было смысле.
Ограничения, касающиеся записи чисел блоками единиц (в даль-
дальнейшем мы будем называть такую запись единичечной) — вместо,
скажем, десятичной записи — и стандартности начальной и ко-
конечной конфигураций (считывания самых левых единиц), несуще-
несущественны; однако некоторые предположения относительно началь-
начальной и конечной позиций машины должны быть сделаны, причем эти
предположения представляются нам чрезвычайно простыми. Мож-
Можно даже описать некоторый процесс, посредством которого всякое
десятичное вычисление преобразуется в вычисление, удовлетворя-
удовлетворяющее приведенным выше условиям A)-E), — процесс, с помощью
которого граф переходов десятичной машины, вычисляющей не-
некоторую функцию, шаг за шагом превращается в граф переходов
машины, вычисляющей ту же функцию, но способом, удовлетворя-
удовлетворяющим условиям A)-E).
Этот процесс в общих чертах таков. Цифры 0, 1,..., 9 кодируем
блоками единиц 1, 11, ..., 1111111111. Тогда, например, десятичное
выражение 213 превращается в 111В11В1111. Нетрудно построить
преобразователь «единичечных» кодов в описанные «кодированно-
десятичные», т.е. машину, которая, будучи запущенной в стандарт-
стандартной конфигурации с блоком из п единиц на ленте, останавливает-
останавливается в стандартной же конфигурации, когда на ленте записано то
же число п, но уже в кодированно-десятичной форме. (Так, при
п = 10 вначале на ленте записано 1111111111, а в заключительной
ситуации — 1151.) Подобным образом можно построить преобра-
преобразователь, решающий обратную задачу. Далее, можно преобразо-
преобразовать граф переходов данной машины, работающей с десятичными
записями, в граф переходов машины, ведущей себя по существу
таким же образом, но работающей с кодами десятичных цифр и
80
6. Функции, вычислимые на абаке
удовлетворяющей условию C). (Последнего можно добиться путем
систематического преобразования графа переходов, в результате
которого всякому движению считывающего устройства влево пред-
предшествовала бы процедура сдвига всех единиц, записанных на ленте,
на одну клетку вправо. А это получается посредством замены ка-
каждой стрелки с пометкой В : L или 1 : L специальным (под)графом,
выполняющим нужный нам общий сдвиг вправо и затем возвраща-
возвращающимся к главной программе в соответствующей позиции.) Теперь
искомая машина, производящая вычисления с выполнением условий
A)-E), получается последовательным соединением преобразовате-
преобразователя единичечной записи в кодированно-десятичную, преобразованно-
преобразованного графа данной десятичной машины и обратного преобразователя
(кодированно-десятичной записи в единичечную).
Описать этот процесс в деталях — весьма трудоемкая работа;
к тому же после всех этих трудов мы все равно не доказали бы, что
единичечная запись так же хороша с точки зрения тыоринговских
вычислений, как всякая другая. Нет конца различным системам
обозначений, которые можно было бы изобрести, и нет надежды
доказать, что что-либо, вычислимое относительно одной из них,
вычислимо и относительно единичечной записи1. Именно по этой
причине мы использовали единичечную запись в качестве отправ-
отправного пункта: определили вычислимость по Тьюрингу как вычисли-
вычислимость, подчиненную условиям A)-E), и интерпретировали
тезис Чёрча: все вычислимые функции вычислимы по Тьюрингу,
в свете этого определения.
Еще один важный аргумент в пользу истинности тезиса Чёрча:
мы покажем, как обычные операции, осуществляемые высокоско-
высокоскоростными компьютерами обычного типа, моделируются на машине
Тьюринга, удовлетворяющей условиям A)-E). Под компьютером
«обычного типа» мы понимаем вычислительное устройство, обла-
обладающее оперативной памятью неограниченного объема. В про-
противоположность машине Тьюринга, записывающей информацию
'В понимании этих вроде бы очевидных вещей нужна определенная осто-
осторожность. Нельзя понимать под системой записи натуральных чисел любую
биективную функцию, отображающую множество слов какого-либо алфавита
на множество натуральных чисел. Эта биективная функция непременно долж-
должна быть вычислимой (относительно чего?) относительно все той же единичеч-
единичечной записи. Таким образом, понятие вычислимости неизбежно проникает уже
в понятие системы записи чисел. — Прим. пере».
6. Функции, вычислимые на абаке
81
символ за символом на одномерной ленте, вдоль которой машина
может передвигаться на один шаг за единицу времени, машина
обычного типа, кажущаяся более мощной, имеет доступ к неогра-
неограниченному числу регистров До, Ri, R%, ..., в каждом из которых
может быть записано число любой разрядности. Таким образом,
машины обычного типа похожи на обобщенную машину Тьюринга,
способную читать и записывать бесконечное множество символов
Sq , Si, 5г,..., каждый из которых может появляться в любой клет-
клетке ее ленты. (Символ Sn изображает число п.) Но машина обычного
типа имеет еще одну способность — прямой доступ, — позволяю-
позволяющую ей переходить непосредственно к регистру й„ без того, чтобы
ползти к нему клетка за клеткой вдоль ленты. Иными словами,
каждый регистр (скажем, Я„) имеет свой собственный адрес (чи-
(число п), позволяющий машине выполнять такие инструкции, как
„ вычислить сумму чисел из регистров Rm ий„и записать ее в
А, регистр Др, .. ..>-*. -
сокращенно обозначаемую нами так: '!
[т] + [п]-+р. ¦'••
(Вообще, [п] обозначает число, записанное в регистре Д„, а число,
стоящее справа от стрелки, является номером регистра, в который
должен быть записан результат операции, изображенной слева от
стрелки.)
Следует отметить, что наша машина обычного типа в одном
отношении очень сильно отличается от реальных компьютеров: хо-
хотя последние часто имеют память прямого доступа, всегда имеет-
имеется верхнее ограничение на величину чисел, которые могут быть
записаны там; например, реальная машина может обладать воз-
возможностью записывать в любом из ее регистров любое из чисел
0, 1, ..., 10000000, но никакое число, большее десяти миллионов,
не может быть записано. Таким образом, вполне возможно, что
какая-либо функция, вычисляемая на одной из наших идеализиро-
идеализированных «обычных» машин, не вычисляется ни на каком реальном
компьютере просто потому, что для некоторых значений аргумен-
аргументов вычисление требует более вместительных регистров, чем это
имеет место на любом реальном компьютере. (Подходящий пример
представляет собой, скажем, сложение: нет никаких ограничений на
, величину чисел, которые может потребоваться сложить, а потому
6-249
82
6. Функции, вычислимые на абаке
невозможны никакие ограничения на величину регистров, требую-
требующихся для записи слагаемых и суммы.) Но это вполне согласуется
с нашим намерением абстрагироваться от технологических огра-
ограничений, чтобы создаваемое понятие вычислимости не оказалось
слишком узким. Мы пытаемся показать, что некоторые функции
невычислимы в абсолютном смысле — невычислимы даже нашими
идеализированными машинами, а потому невычислимы никакими
прежними, теперешними или будущими реально существующими
машинами.
Еще одно соглашение: будем теперь вместо функций, аргумен-
аргументами и значениями которых служат положительные целые числа
1, 2, 3, ..., рассматривать функции с натуральными (неотрица-
(неотрицательными целыми) аргументами и значениями 0, 1, 2, .. .2. Мы де-
делаем это просто для того, чтобы согласовать наш образ действий
с общепринятым и облегчить сравнение того, что делается здесь, с
большинством других книг по этому предмету. Для этого мы про-
просто меняем интерпретацию блоков из одной или нескольких единиц
на ленте машины Тьюринга: теперь он представляет вместо поло-
положительного числа п натуральное число п — 1. Таким образом, при
вычислении 0 + 2 в соответствии с нашими стандартными требо-
требованиями к состояниям ленты мы имеем на ней 15111 в начальный
момент и 111 в заключительный.
Чтобы избежать дискуссии о всевозможных деталях электрон-
электронного или механического устройства машин, будем представлять
себе «обычные» компьютеры устроенными примитивно, на уров-
уровне каменного века. Его регистры мы представляем себе как емкие
нумерованные ящики, способные вместить произвольное число ка-
камешков — ни одного, один, два и т.д., так что [п] есть число ка-
камешков в ящике с номером п. В роли «машины» действует человек,
способный к выполнению двух видов операций:
добавить один камешек к их груде, лежащей в ящике с номе-
номером п,
и
забрать один камешек из груды, лежащей в ящике с номером п,
если там вообще есть хоть что-нибудь.
2Напомним читателю, что такой переход от положительных целых к нату-
натуральным числам в качестве значений аргументов и функций уже совершался
в начале гл. 4, однако теперь для них используется несколько иная система
обозначений. — Прим. персе.
f
6. Функции, вычислимые на абаке
83
Программа задается граф-схемой, определяющей последователь-
последовательность, в которой должны выполняться эти операции (обоих видов).
Типична ситуация, когда программа имеет одну или несколько то-
точек ветвления, в которых следующая операция определяется тем
или иным образом в зависимости от того, пуст или нет ящик, из
которого следует забрать камешек (если это вообще возможно).
Таким образом, точки ветвления ассоциируются с элементарны-
элементарными операциями второго типа (определенными выше). Следуя Ио-
Иоахиму Ламбеку, назовем такую «обычную» машину (бесконечным)
абаком.
Будем использовать обозначения элементарных операций, при-
приведенные на рис. 6-1.
J Ч.
.•Л
Добавьте камешек Если ящик п пуст, то для про-
' t! ' /Г 'ж груде в ящике n *J должения работы сдвиньтесь по
•L'<,,<1' • • V стрелкее, если же нет, то, удалив
j из ящика один камешек, сдвинь-
сдвиньтесь по другой стрелке ... ,
li ' vt Рис. 6-1. Элементарные операции в абаке. »ИГ .) и
Процесс построения граф-схем иллюстрируется
примерами.,.
Пример 64. бчистит* fount с вомероы п
1...«'. >, Я,
;!'. Г:
Граф-схема
Блок-схема
84
6. Функции, вычислимые на абаке
Пример 6.2. Перенести содержимое ящика с номером т в
ящик с номером п (где т^п) ф
Граф-схема
л.
Блок-схема
(В случае m = n программа останавливается либо сразу —
выходя на е-стрелку, — либо никогда в соответствии с тем,
пуст этот ящик в начальный момент или нет.) Бели же (что
и имелось в виду) тпфп, то результат выполнения програм-
программы будет в точности тот же, что и при перекладывании камеш-
камешков по одному из ящика m в ящик п, пока первый из них не
опустеет, но у нашего пещерного человека нет инструкций, за-
заставляющих его поступать именно так. Умеет он лишь одно
из двух: (т—) — вынуть из ящика т один камень за едини-
единицу времени и выбросить его наземь и (п+) — поднять с зем-
земли камень, опять-таки один за единицу времени, и положить
его в ящик п. Нет никакой уверенности в том, что он поло-
положит в ящик п те самые камешки, которые вынул из ящика т,
но нам и не нужно подобной уверенности, чтобы знать, что до-
достигнут результат, предписанный данной блок-схемой, а имен-
именно
[т] + [п] —> п: число камешков в ящике п после этого перемеще-
перемещения равно сумме чисел камешков в ящиках гаипдо перемеще-
перемещения.
а также
0-tfn: число камешков в ящике m после этого перемещения
равно нулю.
Вообще, число, стоящее справа от стрелки, является номером ящи-
ящика (регистра памяти, груды), а число слева от этой стрелки есть
число камешков, которые окажутся в этом ящике (регистре памяти,
6. Функции, вычислимые на абаке
85
груде) после того, как рассматриваемое перемещение будет выпол-
выполнено.
Отныне предполагается (если только явно не оговорена проти-
противоположная возможность), что если ящики нумеруются буквами
т, п, р и т.д., то различные буквы обозначают различные ящи-
ящики.
Пример 6.3. Добавить число из ящика т в ящик п без
опустошения ящика m
Чтобы программа давала предписанный результат, ящик р дол-
должен быть пустым как при начале ее выполнения, так и по выпол-
выполнении этой программы. ,
t-i
Граф-схема
Блок-схема
Более общее описание действия этой программы без к
специальных предположений относительно [р] таково:
с-либо
Ни
N-
Ни
0
-»• п,
—> т
-* Р-
Как и обычно, здесь вертикальный порядок записи, сверху вниз, со-
соответствует порядку выполнения действий. Таким образом, ящик р
опустошается после того, как выполнены другие два действия. (По-
(Порядок выполнения двух первых действий произволен: если их поме-
поменять местами, результат будет тот же самый.)
86 6. Функции, вычислимые на абаке
Пример 6.4. Умножение
Сокращенней граф-схема
Блок-схема
Полная граф-схема
Числа, которые надо перемножить, располагаются в различных
ящиках с номерами rai и ш2; два других ящика, п и р, в начальный
момент пусты. Произведение оказывается в ящике п. Вместо то-
того чтобы создавать соответствующую граф-схему на пустом месте,
мы вставим в нее блок-схему примера 6.3 как уже готовый узел. То-
Тогда сразу можно нарисовать и полную граф-схему, как это сделано
справа (где лишь m из примера 6.3 заменено на т2). Процедура со-
состоит в многократном добавлении [гаг] камешков в ящик п с исполь-
использованием ящика mi в качестве счетчика: перед каждой операцией
добавления мы удаляем один камешек из ящика rai, так что когда
он оказывается пустым, в ящике п имеется [т2] + [гаг] + ... + [т2]
камешков. "
[т.]
Пример 6.5. Возведение в степень
Подобно тому как умножение есть итерированное сложение,
возведение в степень (экспоненцирование) является итерирован-
итерированным умножением: чтобы возвести х в степень у, перемножьте
у штук х-в:
ху = х • х ¦... ¦ х.
Программа строится совершенно прямолинейно, если только про-
программу умножения из примера 6.4 изменить так, чтобы она дава-
давала [т2] • [п] —<• п, — см. сокращенную граф-схему возведения в сте-
степень. Необходимое изменение процедуры из примера 6.4 получается
6. Функции, вычислимые на абаке
87
:** ," Jn2l:Mг*_ ? J
e Же ¦ <g
Кумулятивное
умножение
[т2] • [п] -> п
[п]
•[та] -
0 -¦
(пример 6.4)
Я
п
Сокращенная граф-схема
возведения в степень
¦•¦»:
Кумулятивное умножение
(следуя Питеру Тови) присоединением к ней процедуры приме-
примера 6.2 — см. блок-схему кумулятивного умножения. Если в на-
начальный момент ящики п, р и q пусты, то программа возведения в
степень дает требуемый результат:
О
гах
совершенно аналогично программе умножения из примера 6.4 —
см. его блок-схему. Строение сокращенных граф-схем для умноже-
умножения и возведения в степень различается лишь тем, что в случае
возведения в степень необходимо вначале положить один камешек
в ящик п. Поэтому если [rai] = 0, то мы по выполнении програм-
программы получаем [п] = 1 (причем получаем тотчас, без обращения к
процедуре умножения). Это соответствует соглашению
для любого натурального х. Если же [mi] положительно, то по вы-
выполнении программы [п] окажется произведением [mi] и [т2] в со-
соответствии с итерированным применением правила
реализуемого с помощью кумулятивного умножения с использова-
использованием ящика mi в качестве счетчика.
Теперь должно быть понятно, что исходное ограничение двумя
типами элементарнейших действий, п+ и п—, не препятствует нам
88
6. Функции, вычислимые на абаке
6. Функции, вычислимые на абаке
89
в вычислении довольно сложных функций, например всех функций
из серии, начинающейся суммой, произведением, экспонентной, ,..,
где (п + 1)-й элемент серии получается итерированием n-го элемен-
элемента. В частности, следующий элемент этой серии, суперэкспонента,
определяется как
sup(z,y) =
<r, t
так что
, sup(z,O) = l,
и соединение в общую схему дает (например, для у = 4)
(Расстановка скобок существенна: З^3 ) = З27, т.е. является произ-
произведением 27 троек, а (З3) = 273, что является произведением трех
двадцати-семерок, или всего 9 троек.) Понятно, что граф-схема ма-
машины, вычисляющей суперэкспоненту, получается из граф-схемы,
вычисляющей экспоненту (т.е. возводящей в степень), так же, как
граф возведения в степень получается из графа матицы умножения
из примера 6.5.
Доказав, что некоторые весьма сложные функции вычисляются
на абаке, приведем теперь некоторые аргументы в пользу тезиса
Чёрча: мы докажем, что всякая функция, вычислимая на абаке, вы-
вычислима и по Тьюрингу. Мы сделаем это, предложив некоторый
метод преобразования произвольной программы на абаке в граф-
схему машины Тьюринга, вычисляющей ту же функцию, что и ис-
исходная абак-программа. При этом характер вычисления на машине
Тьюринга будет стандартным, описанным в начале этой главы. Но
прежде чем заняться описанием нашего метода, преобразующего
граф-схемы абака в граф-схемы эквивалентных машин Тьюринга,
мы должны в определенном смысле стандартизировать вычисле-
вычисления на абаке: мы должны знать, где искать в начальный момент
значения аргументов функции, вычисляющейся на абаке, и где в
заключительный момент искать значения самой функции. Следую-
Следующие соглашения так же хороши, как и все прочие.
Правила вычисления функции f(x\,X2,.. . ,хг) на абаке. В на-
начальный момент значения аргументов задаются как числа ка-
камешков в первых г ящиках, причем все остальные ящики пусты:
xi = [1], ..., хг = [г], 0 = [г + 1] = [г + 2] = .... В заключительный
момент значением функции является число камешков в некото-
некотором заранее указанном ящике п (который может, но не обязан
быть одним из первых г ящиков). Таким образом, в момент, ко-
когда вычисление останавливается, т.е. когда мы попадаем на стрел-
стрелку граф-схемы, не ведущую ни в какую вершину, мы получаем
f(xi,...,xr) = [n]. Если же вычисление никогда не останавлива-
останавливается, то f(x\,..., хг) не определено.
Отметим, что наши программы для сложения, умножения
и возведения в степень из примеров 6.3-6.5 имеют по суще-
существу эту же форму с г = 2 в каждом случае. Мы описывали
их, не уделяя внимания этим деталям, так что вопрос о том,
в каких именно ящиках должны содержаться значения аргумен-
аргументов и функции, оставался открытым; например, в случае про-
программы сложения в примере 6.3 мы лишь указывали, что зна-
значения аргументов хранятся в различных ящиках с номерами
шип, что значение функции находится в ящике п и что тре-
третий ящик, с номером р, первоначально пустой, также использу-
используется в процессе вычисления. Теперь же мы должны определить
п», п и р, потребовав, чтобы тип стали 1 и 2 (в любом по-
порядке), а р стало бы каким-либо числом, большим, чем 2. Так,
можно принять п = 1, m = 2, р = 3, получив в этом случае про-
программу сложения, удовлетворяющую стандартным требованиям
(рис. 6-2).
¦А-
¦> ¦*.-
Рис. 6-2. Сложение (пример 6.3) в стандартном формате.
Стандартные правила вычисления ставят в соответствие ка-
каждому абаку некоторую функцию из натуральных чисел в на-
натуральные, стоит только задать число г аргументов функции
90
6. Функции, вычислимые на абаке
и номер п ящика, в котором должны появиться ее значения.
Подобным же образом стандартные правила вычисления на ма-
машинах Тьюринга ставят в соответствие каждой машине Тью-
Тьюринга определенную функцию, аргументы которой и сама функ-
функция принимают положительные целые значения, стоит лишь за-
задать число г ее аргументов. Отметим, что если мы стандарт-
стандартным образом зададим граф-схему абака А, то для каждого его
регистра п, который можно назначить для хранения результа-
результата вычислений, существует бесконечно много функций Агп, вы-
вычисляемых данным абаком — по одной для каждого возможно-
возможного числа аргументов. Так, если задать А как простейший абак
для сложения из примера 6.2, то при п = 1 и m = 2 мы полу-
получим
А\{х,у) = х + у
для любых натуральных х и у, но, помимо этого, мы будем иметь
также тождественную функцию А\ = х одной переменной, а для
трех и более аргументов — функции A\(xi,X2, ¦¦ -,хг) = х^ + х%.
Даже для г = 0 мы можем считать, что А вычисляет некото-
некоторую «функцию» определенного типа, а именно число А° = 0 еди-
единиц в ящике 1, когда вычисление заканчивается, начавшись, ко-
когда все ящики (кроме первых г) пусты. Таким образом, ситу-
ситуация полностью аналогична тому, что мы имели в случае ма-
машин Тьюринга, каждая из которых тоже, согласно стандарт-
стандартным правилам, вычисляла по функции г аргументов для каждого
г = 0, 1, 2, ....
Установив стандартные правила для вычислений обоих типов,
мы можем вернуться к проблеме построения метода, позволяюще-
позволяющего граф-схему произвольного абака А„, в котором яшик п выделен
для хранения значений функций, превращать в граф-схему маши-
машины Тьюринга, вычисляющей те же функции: для каждого г эта
машина Тьюринга вычисляет ту же функцию Атп от г аргумен-
аргументов, что и данный абак. Наш метод описывает машину Тьюринга,
граф-схемой которой следует заменить каждую вершину типа п+
в граф-схеме данного абака вместе с выходной стрелкой этой вер-
вершины, некоторую машину Тьюринга, граф-схемой которой следует
заменить каждую вершину типа п— вместе с ее двумя выходными
стрелками, и, наконец, машину Тьюринга, которая в конце работы
стирает на ленте все, кроме n-го блока единиц, и останавливается,
считывая самую левую из оставшихся единиц.
6. Функции, вычислимые на абаке
91
Важно уяснить соотношение между ящиками абака и соответ-
соответствующими частями ленты машины Тьюринга. Пример: при вы-
вычислении значения Л* @,2,1,0) начальные конфигурации на лен-
ленте и в ящиках такие, как показано на рис. 6-3. Ящики, со-
Лента:Т
Ящики:
LJ I ¦ . I l . l LJ LJ LJ
R3
R*
Re
Rr
>" ' '.",! Рис. 6 — 3. Соответствие между ящиками и
¦> ч: участками ленты (¦ = один камешек).
держащие один, два, ... камешков, представляются блоками из
двух, трех, ... единиц на ленте (см. рис. 6-3). Одиночные про-
пробелы разделяют на ленте блоки, соответствующие последователь-
последовательным ящикам. Всякий пустой ящик представляется одной клеткой,
которая может содержать пустой символ (см. R$, Re, Rt, ...)
или единицу (см. R\ и R$). В произвольный момент времени еди-
единица соответствует пустому ящику, если правее на ленте есть
еще хоть одна единица, в начальный же момент единицы соот-
соответствуют пустым аргументным ящикам (с R\ no Rr), а пустые
символы — ящикам Rr+i, Rr+2, Таким образом, в любой
момент вычисления мы, обнаружив в процессе движения впра-
вправо (влево) два пробела подряд, можем быть уверены, что ни-
нигде далее вправо (влево) на ленте нет ни одной единицы. Число
единиц в блоке на ленте, соответствующем той или иной клет-
клетке, может по мере развертывания программы расти или убы-
убывать в зависимости от содержимого этого ящика, а также сдви-
сдвигаться по ленте вправо или влево в зависимости от того, при-
прибавляются или убывают камешки в ящиках, расположенных ле-
вес.
Теперь можно описать первый шаг нашего метода преобразова-
преобразования граф-схемы абака в граф-схему эквивалентной машины Тью-
Тьюринга: каждая вершина типа s+
\i
92
6. Функции, вычислимые на абаке
1:1
О О С С
В:1 1:Я В:\ \:R
Запишите 1 в пустой клетке справа
от «-го блока
следующий блок
на одну клетку
вправо
Вернитесь х
самой левой 1
на ленте
Рис. 6-4. Граф-схема узла, заменяющего вершину »+.
заменяется экземпляром (в-\-)-граф-схемы, которая изображена на
рис. 6-4. Первые 2s вершин («+)-графа переводят машину Тью-
Тьюринга из ее стандартного положения, в котором она считыва-
считывает самую левую единицу на ленте, на пустой символ, располо-
расположенный непосредственно справа от s-ro блока единиц. (Разыс-
(Разыскивая s-й блок, машина заменяет В-представление каждого пу-
пустого блока его 1-представлением.) Покинув вершину sb, маши-
машина записывает 1, сдвигается на одну клетку вправо и делает
тот или иной ход (в вершине х) в зависимости от того, считы-
считывает она при этом пустой символ или 1. Бели она считывает
пустой символ, то правее больше не может быть единиц, и по-
потому машина возвращается в начальную позицию. Но если она в
этот момент считывает 1, то она должна еще поработать, пре-
прежде чем вернуться в стандартную позицию, так как справа на
ленте есть еще блоки единиц, нуждающиеся в обработке. Их тре-
требуется передвинуть на одну клетку вправо, стерев в каждом бло-
блоке первую единицу и, наоборот, заполнив единицей пробел спра-
справа от блока и продолжая эту работу до тех пор, пока машина
не наткнется на пробел справа от последнего пробела, заполнен-
заполненного ею единицей. С этого момента справа не может быть бо-
более единиц, и машина возвращается в свою стандартную пози-
позицию.
Отметим, что вершина 1а нужна для вычисления функции
г = 0 аргументов — в этом случае «функция» Л°, вычисляемая аба-
абаком, есть число. Отметим также, что первые я — 1 пар вершин (вме-
(вместе с выходящими из них стрелками) совершенно одинаковы, в то
время как последняя пара отличается от них только тем, что стрел-
стрелка, ведущая из вершины sb вправо, помечена В : 1 вместо В : R.
6. Функции, вычислимые на абаке
1:1
93
ВЛ
Рис. 6-5. Граф-схема машины, заменяющей в+, в случае • = 1.
Опишем теперь второй шаг процесса преобразования граф-
схемы абака в граф-схему эквивалентной машины Тьюринга: ка-
каждая вершина типа s—
к /-..,
заменяется экземпляром (s—)-граф-схемы, которую вы можете по-
построить, руководствуясь блок-схемой рис. 6-6. В результате вы-
выполнения первого и второго шагов нашего метода граф-схема абака
преобразуется в объект, не являющийся в точности граф-схемой
машины Тьюринга, вычисляющей те же функции, что и данный
абак. Граф может оказаться неполноценным в двух отношениях.
Во-первых, если данный абак когда-либо останавливается, в нем
должны быть одна или несколько «холостых» стрелок — стрелок, не
ведущих ни в какую вершину. Достаточно просмотреть (в-(-)-граф-
схему и блок-схему (s—)-графа, чтобы убедиться, что в этом случае
граф нашей машины Тьюринга будет иметь одну или более стрелок
вида
л ¦ • ¦
не ведущих ни в какую вершину. Но в граф-схеме полноцен-
полноценной машины Тьюринга каждая стрелка должна заканчиваться в
некоторой вершине. Мы можем исправить этот дефект, просто
пририсовав изолированные вершины на концах холостых стре-
стрелок:
94
6. Функции, вычислимые на абаке
Сдвиньтесь к первой 1 в я-м блоке
(замени по ходу движения
В-представления пустых регистров на
1-представления)
1: Л
Верно ли [з] = О?
V.R (Нет)
Найдите и сотрите
самую правую 1 в
блоке. Напишите 1
перед всеми
единицами,
которые могут быть
в следующем блоке
направо.
Есть л* они там?
1:Я (Да)
Вернитесь к
стандартному
положению
и ¦
1 4 A'AtJXi ll.4t"
¦r
Вернитесь к
стандартному
положению
В Я
Рис. 6-6. Блок-схема узла, заменяющего вершину я—.
При этом, однако, может остаться вторая погрешность: при вычи-
вычислении функции Arn(xi xr) машина Тьюринга должна остана-
останавливаться на самой левой единице, присутствующей на ленте, но
значение функции изображается п-м блоком единиц на ленте. Да-
Даже если п = 1, мы не можем зависеть от того, что на ленте после
первого блока не окажется единиц, и поэтому наш метод нуждается
еще в одном шаге.
Третий шаг: выполнив первые два шага преобразования, пе-
переделайте все холостые стрелки так, чтобы они заканчивались
б. Функции, вычислимые на абаке
95
во входной вершине графа очистки, который вам предлагает-
предлагается построить. Этот граф заставляет машину (которая в нача-
начале выполнения этой процедуры считывает самую левую едини-
единицу на ленте) стереть все, кроме первого блока единиц, если
п = 1, и остановиться, считывая самую левую из оставшихся еди-
единиц. Если же пф\, то она стирает на ленте все, кроме са-
самой левой имеющейся там единицы и всего n-го блока, пере-
перемещает все его единицы, кроме самой правой, на позиции не-
непосредственно справа от самой левой единицы ленты, стира-
стирает уцелевшую самую правую единицу и затем останавливается,
считывая самую левую единицу. В обоих случаях в результа-
результате самая левая единица блока, представляющего значение функ-
функции, оказывается именно там, где самая левая единица была
первоначально.
Выполнив во всех деталях второй и третий шаги, описан-
описанные выше, вы установите, что все функции, вычисляемые на
абаках, вычислимы и по Тьюрингу. Это добавляет убедитель-
убедительности тезису Чёрча, поскольку функции, вычисляемые на аба-
абаках, — это функции, допускающие вычисление на современных
цифровых вычислительных машинах, если только при их рас-
рассмотрении отбросить ограничения, касающиеся числа и объема
регистров оперативной памяти. Разумеется, сохраняется возмож-
возможность того, что в один прекрасный день будут изобретены су-
существенно отличные типы вычислительных машин — маши-
машины, которые при соответствующей идеализации оказались бы
в состоянии вычислять функции, не вычислимые ни на аба-
абаках, ни на машинах Тьюринга. (Не зная, как будут функци-
функционировать эти машины, мы не можем и решить, какая иде-
идеализация потребуется. Можно предположить, однако, что эта
идеализация будет сходна с применявшейся нами при рассмо-
рассмотрении машин Тьюринга и абаков и касавшейся возможностей
их памяти: машина Тьюринга имеет большее пространство на
ленте, чем ей реально требуется, и, аналогично, абак облада-
обладает пространством в своих регистрах для неопределенного коли-
количества неопределенно длинных чисел.) С математической точ-
точки зрения тезис Чёрча остается недоказанным. Скорее мы по-
получаем подтверждение его убедительности, подобное тому, ка-
какое могла бы получить эмпирическая научная теория. Новые ар-
аргументы в пользу тезиса Чёрча содержатся в следующих двух
главах.
96
Упражнения
6. Функции, вычислимые на абаке
6.1. Постройте (в—)-граф-схему (т.е. проделайте второй шаг в
процессе преобразования граф-схемы абака в граф-схему эквива-
эквивалентной машины Тьюринга).
6.2. Постройте граф очистки (третий шаг того же процесса).
6.3. Проблема остановки для абаков. Пусть h(x, у) = О или 1
в зависимости от того, останавливается когда-либо или нет
абак с номером х в некотором списке всех абаков, если его
запустить с у камешками в регистре R\ при пустых про-
прочих регистрах. Докажите (без помощи аналога тезиса Чёрча
для абаков), что функция ft не вычислима ни на каком аба-
абаке. Указание. Скопируйте рассуждение, приведенное в конце
гл. 5.
6.4. Проблема усердного абака. Если абак, в начале работы ко-
которого все его регистры пусты, никогда не останавливается, то его
продуктивность считается равной нулю; в противном случае его
продуктивностью считается количество камешков в R\, когда он
останавливается. Пусть р(п) равно продуктивности самого продук-
продуктивного абака с п вершинами. Докажите, что функция р не вычи-
вычислима на абаках.
V"
*» I
Решения
41!. -
6.1. Верхний блок в блок-схеме (s—)-графа содержит граф, иден-
идентичный части («+)-графа, заключенной между вершинами 1а и sa
(включительно). Стрелка с пометкой 1 : R, выходящая из нижней
части этого блока, соответствует стрелке, выходящей вправо из
вершины so в (Н-)-граф-схеме.
Блок «Верно ли, что [s] — О?» не содержит ничего, кроме начал
двух исходящих стрелок: они выходят из вершины, изображенной
вверху этого блока.
Блоки «Вернитесь в стандартную позицию» повторяют устрой-
устройство части (в+)-графа, расположенной справа от вершины х; стрел-
стрелки с пометками В : L, входящие в эти блоки, соответствуют стрелке |
В : L, исходящей из вершины х.
Единственным новшеством является оставшийся блок «Найдите
и сотрите ...». Этот блок содержит граф, изображенный на следу-
следующей странице.
6. Функции, вычислимые на абаке
¦1-Я
97
вл
Найдите самую правую 1
в блоке
Сотрите ее , " ¦,
Напишите 1 перед всеми
единицами, которые могут
быть в следующем блоке
Есть они там?
B:L (Нет) / \ 1-Я (Да)
6.2. Граф очистки (п ф 1).
V.L
B.L
п - 1
V' таких
узлов
¦ Ь
1:В1 JB.R
j Сотрите все
¦ между самой
левой 1 и п-м
блоком
Перепрыг-
Перепрыгните через
n-й блок
1-Я
Л
1.в/\в
JB:R\
Найдите самую
левую 1 в
блоке
B.L
г\
:L\jfl:t
;:Я V*'
п-м
1:1
Г\
\ГВ:.
А ¦
Сотрите
Есть ли
еще 1
вправо?
В.Я(
1:Я
\:В
)
В L
(Нет)
(Да^С
1:Я
В:\ )
< С
последнюю 1 в
п-м блоке,
найдите самую
левую 1 и
остановитесь,
считывая ее
' Сотрите
самую
1:В левую 1 в
i п-м блоке и
*) запишите 1
справа от
1:Я самой
правой 1
« слева от
¦* n-го блока
Сотрите все единицы
справа от n-го блока
(Мы благодарны М. Пендлбери,
построившему эту машину)
6.3. Пусть ft = #2 для некоторого абака Н, т.е. пусть Я вычи-
вычисляет функцию Л и хранит ее значения в регистре Л„. Тогда для
всякого х абак, изображенный на приводимом в этом абзаце гра-
графе, запущенный с х камешками в регистре R\, останавливается в
точности тогда, когда абак с номером х, запущенный с теми же
х камешками в Ri, не останавливается вовсе, — причем в каждом
случае все регистры, кроме Ri, предполагаются первоначально пу-
пустыми. (Отметим, что если в рассматриваемом абаке удалить по-
7—249
98
6. Функции, вычислимые на абаке
следнюю вершину, то он будет вычислять функцию h(x,x).) Если
абак Н с указанными свойствами существует, то существует и сле-
следующий абак:
Граф из примера 6.3 при
то = 1,п = 2, р = 3
Граф
абака Я
Граф абака номер т
Свободные
стрелки
абака Н
а потому он должен присутствовать в нашей нумерации всех аба-
абаков, находясь в ней под номером, скажем, т. Но, полагая х = т,
мы видим, что абак с номером т, запущенный с т камешками в
регистре Ri и всеми остальными пустыми регистрами, останавли-
останавливается тогда и только тогда, когда он не делает этого. Значит,
такого абака не существует, а потому никакой абак не вычисляет
функцию h и проблема остановки абаков неразрешима.
6.4. Пусть какой-либо абак Р вычисляет функцию р, записывая
ее значения в регистр 1. (Если какой-либо другой абак вычисляет
функцию р, но записывает ее значения в регистр п, то мы можем
превратить его в абак искомого типа, добавив три дополнительные
вершины: одну для очистки регистра Ri и, подобно примеру 6.2,
еще две, чтобы перегрузить содержимое Д„ в регистр Ri.) Если
абак Р Имеет it вершин, то машина, граф которой приведен ниже,
имеет п + 2к вершин и продуктивность р(р(п)).
п вершин
Поэтому если Р существует, то '"'¦"-
р(п + 2к)>р(р(п))
для всех п. Легко доказывается, что р(п) — возрастающая функ-
функция переменного п, так как, взяв в качестве А один из наиболее
продуктивных абаков с п вершинами, мы, добавляя единственную
A+)-вершину, получим более продуктивный абак с п + 1 вершина-
вершинами:
6. Функции, вычислимые на абаке
Отсюда следует, что
п + 2к > р(п)
99
(*)
для всех п, если только указанный абак Р существует. Потратив
п вершин, мы можем поместить п камешков в регистр R\, а с по-
помощью еще пяти вершин, воспользовавшись процедурой из приме-
примера 6.3, скопировать содержимое Ях (т.е. упомянутые п камешков) в
регистр Яг- Добавляя еще один экземпляр схемы из примера 6.3, мы
получим абак с п + 10 вершинами, имеющий продуктивность 2п.
Таким образом, для всех п справедливо
р(п + 10) > 2п,
существует абак Р или нет. Заменяя в неравенстве (*) число п на
п + 10 и используя также наше последнее неравенство, получим
п + 10 + 2Jk > 2п
для всех п, если только Р существует. Поэтому если Р существует,
то
10 + 2Jfc > п я>
для всех п. Подставляя вместо п число 11 + 2Jb, получим
если только абак Р существует. Значит, такого Р нет и проблема
усердного абака неразрешима.
Замечание. Изложение теории абаков в этой и следующих гла-
главах основывается на следующей работе Ламбека: Lambek J. How
to program an infinite abacus, Canad. Math. Bull., 4 A961), 295-
302; исправления: 5 A962), 297. Абаки Ламбека представляют со-
собой упрощенный вариант машин, изучавшихся Мелзаком в работе:
Melzak Z. A. An informal arithmetical approach to computability and
computation, Canad. Math. Bull., 4 A961), 279-293.
7. Рекурсивные функции вычислимы на абаках
101
Первого и последнего из этих равенств,
Рекурсивные функции вычислимы на
абаках ,-. v < «
г ,-г
Все функции из последовательности «сумма, произведение, экс-
экспонента, ...», рассматривавшиеся в гл. 6, принадлежат классу при-
примитивно рекурсивных функций. Мы дадим здесь точные определе-
определения этого класса и более обширного класса R рекурсивных функций.
Затем мы докажем, что все функции класса R принадлежат клас-
классу А функций, вычислимых на абаках, откуда следует, что ,
' .,>.••,¦-,»¦. ' V, ДСЛСТ, i...: ¦. «/W • ¦-;¦.¦¦:':, -.- ,t ¦*>*.
. '¦ * ¦ '/,/¦¦
где цифры под знаками включения суть номера глав, в которых эти
включения доказаны. Это служит еще одним подтверждением тези-
тезиса Чёрча, поскольку мы увидим, что класс рекурсивных функций в
действительности очень широк — настолько, что правдоподобным
выглядит предположение о рекурсивности всех функций, вычисли-
вычислимых в каком бы то ни было интуитивном смысле.
Для выявления руководящих нами идей рассмотрим третью
функцию приведенной выше последовательности, функцию ехр, ко-
которая, будучи применена к паре значений аргументов (х,у), дает
у-ю степень числа х:
Очевидно,
что
t <
х°=1,
х^х,
- х2=х-
xvlx-
X
X
У
X
и. % ¦
¦;. ¦
¦...¦X,
раз
•... • х ¦ х
1
V
= х-х*.
»• '-Ф
достаточно для вычисления всех значений функции. '
Пример. Вычисление значения 5s
53 = 52+1 = 5 • 52 (полагая х=5 и у=2 в последнем равенстве),
52 = 51+1 = 5 • 51 (полагая х=5 и у=1 в последнем равенстве),
51 = 50+1 =5-5° (полагая х=5 и у=0 в последнем равенстве),
5° = 1 (полагая х=5 в первом равенстве).
Объединяя эти равенства, получим
Таким образом, мы свели задачу о вычислении экспоненты к за-
задаче о вычислении произведения. Последняя подобным же образом
сводится к задаче о вычислении сумм, а та в свою очередь может
быть сведена к последовательному прибавлению единиц. Итоговым
результатом этих вычислений является информация о том, что
53=
53=1
у+ 1 раз
125 единиц
Фактически мы выразили здесь 53 с помощью некоторого вариан-
варианта единичечной записи, где числа нуль и единица изображаются
символами 0 и 1 и где изображение числа п + 1 получается из изо-
изображения числа п путем присоединения символа +1.
Чтобы подчеркнуть, что мы не пытаемся протащить операцию
сложения в наши обозначения для чисел, мы будем использовать
символ s для обозначения функции следования, обозначая последо-
последовательные натуральные числа таким образом:
0, «@), >(>@)), ....
Итак, наша официальная единичечная система обозначений явным
образом соединяется с символом s одноместной функции, которая,
будучи применена к произвольному натуральному числу в качестве
аргумента, дает следующее по величине натуральное число как зна-
значение. Теперь становится ясным, что, например, пара равенств
х + 0 = х, х + s(y) = s(x + у)
102
7. Рекурсивные функции вычислимы на абаках
содержит информацию, которой, пусть даже неявным образом, нет
в обозначениях натуральных чисел.
Пример
Вычисление 2 + 3, т.е. s(s@)) + s(s(s@))).
s(s@)) +s(s(s@))) = s(s(s@)) + s(s(O))) (второе равенство), * *
x у x у
s(s@)) +s(s@)) = s(s(s(O)) + s@)) (второе равенство),
= s(s(s@)) +0) (второе равенство),
\
= s(s@))
(первое равенство).
Соединяя эти соотношения, получаем
•(«@)) + *(«(«@))) = S(S(S(O)) + 8(8@))) =
':,<- = *(*('(«@))+«@)))= *.
• . = s(s(s(s(s@))+0))) =
Полюбовавшись на формулы, использующие бескомпромисно фор-
формальные обозначения, мы можем ввести выражения
sO, ssO, sesO, ... ¦;,., ч
в качестве сокращений для
.(О), ф@)), s(s(s@))), ...
удалением всех пар скобок, кроме главных, помогая человеческо-
человеческому восприятию формул. С использованием этих сокращений равен-
равенства, определяющие сложение, принимают вид
х + 0 = х, х + sy = s(x + у),
а вычисления протекают следующим образом:
ssO + sssO = s(ssO + ssO),
ssO + ssQ = s(ssO + s0),
ssO + s0 = s(ss0 + 0),
ssO + 0 = ssO.
7. Рекурсивные функции вычислимы на абаках 103
Объединяя эти соотношения, получаем
880 + 8880 = s(ssO + SSO),
,,• " ,.'' ' ,,.. , , =s(s(ss0 + S0)),
л. ^ ;; , = s(s(s(s80 + 0))),
= s(s(s(ssO))) = sssssO,
где последний шаг состоит в мысленном переписывании ssO в виде
s(s@)) с последующей заменой выражения s(s(e(e(s@))))) сокра-
сокращенным sssssO.
Другим принятым обозначением функции следования служит
штрих, который ставится справа сверху от аргумента. В этом слу-
случае (без использования скобок) последовательные натуральные чи-
числа записываются в виде
0, 0', 0", ....
•у
а равенства для сложения принимают вид
Причина использования такой перестраховочной системы обо-
обозначений, при которой вместо 3 пишется s(s(s@))) и т.п., состоит
в том, что мы применяем к хорошо знакомому способу вычисления
детальный анализ, применявшийся нами к вычислениям на маши-
машине Тьюринга и на абаке. Необходимость ясности в подобного ро-
рода мелочах заставляет нас быть осторожными при использовании
употребительных сокращений до тех пор, пока мы не убедимся в
их пригодности в рассматриваемом контексте. Чтобы достичь по-
подобной ясности, мы должны со всей четкостью ориентироваться в
изучаемых понятиях. Достичь этого можно многими равноценными
путями. При этом, видимо, каждый из них имеет некоторые свой-
свойства, представляющиеся не слишком естественными в силу их про-
произвольности. Выбор системы обозначений, использующей символ s,
является тривиальным первым шагом по направлению к явности
определений. Стремление к полноте объяснений вынуждает нас к
некоторым дальнейшим шагам на пути, кажущемся сейчас наибо-
наиболее простым и являющемся в действительности наиболее обычным.
Мы определим класс примитивно рекурсивных функций, ука-
указав некоторый исходный запас принадлежащих этому классу функ-
функций, а также два вида операций, которые, будучи применены к
104
7. Рекурсивные функции вычислимы на абаках
элементам нашего класса, приводят к функциям, по определению
также принадлежащим ему. Для полноты определения оговоримся,
что никакая функция не зачисляется в определяемый класс, пока
она не будет обнаружена в нашем исходном запасе или же полу-
получена из функций этого запаса путем конечного числа применений
упомянутых операций.
Исходный запас функций содержит нуль-функцию, функцию сле-
следования и различные проектирующие функции.
Нуль-функция, обозначаемая z, есть функция одной переменной.
Она принимает нулевое значение для каждого натурального значе-
значения аргумента:
г(х) = 0. ' Jt
Таким образом, . :; ?я < i;
или, в s-системе обозначений,
= ... = o. •*•¦¦¦ ¦
Мы уже имели дело с функцией следования s, зависящей от
одной переменной и приписывающей всякому натуральному чи-
числу следующее за ним натуральное число в качестве значения.
Таким образом, s@) = 1, s(l) = 2, sB) = 3, Записанные в си-
системе s-обозначений, эти равенства становятся тавтологичными
(s@) = s@) и т.п.), поскольку свойства функции s включены в обо-
обозначения.
Проектирующая функция id одной переменной приписывает вся-
всякому натуральному числу, выступающему в качестве значения ар-
аргумента, то же самое число и как значение функции:
id(x) = х.
Проектирующих функций, зависящих от двух переменных, име-
имеется две, idj и id|. Первая и вторая из них выбирают из всякой
пары натуральных чисел, выступающих в качестве значений аргу-
аргументов, соответственно первое и второе:
id21(x,y) = x, idl(x,y) = y.
(В терминах аналитической геометрии величины id1(ar, у) и id2(z, у)
суть проекции х и у точки (х, у) плоскости на оси X и Y
7. Рекурсивные функции вычислимы на абаках
105
соответственно.) Вообще, для всякого положительного целого п
существует п проектирующих функций от п переменных, выби-
выбирающих соответственно первое, второе, ..., n-е во всяком наборе
п чисел:
Для функции id, тождественной функции одной переменной, име-
имеется очевидное альтернативное обозначение, id}. Проектирующие
функции часто называют еще функциями выбора.
Из исходного запаса базисных функций — функций z, s и бес-
бесконечной серии проектирующих функций id, idj, id|, id', ... — мы
можем строить новые примитивно рекурсивные функции с помо-
помощью операций двух видов: композиции и примитивной рекурсии.
Таким образом, примитивно рекурсивные функции — это просто
базисные функции вместе со всеми функциями, которые можно по-
получить из базисных путем конечного числа применений указанных
операций (в любом порядке).
Операция первого типа, композиция (она же подстановка), зна-
знакома всем. Бели / — некоторая функция m переменных, а д\,
• ••,9т — функции п переменных каждая, то функция Л, опреде-
определяемая равенством
i,.... хп),...,
i,..., хп)),
(Сп)
называется функцией, полученной из /, д\, ..., дт в результате
композиции. Можно также изобразить этот факт сокращенно:
* ¦¦>• h = Cn[f,9l,...,gm]. •¦
Пример - -- ".
Функция Л трех переменных, значением которой служит число,
следующее за ее третьим аргументом, получается с помощью ком-
композиции из функций s и id|: h = Cn[s,id|]. В терминах соотноше-
соотношения (Сп) мы имеем п = 3 н m = 1, т.е. имеем дело с частным случа-
случаем этого определения вида h(xi,X2, *з) = /(<7i(*i> *2, *з)), где / = s
и fli = id|.
Другой пример. Сп[ в, я ]
Результатом этой композиции является функция одной перемен-
переменной х, значением которой служит х + 2, т.е. s(s(x)). В обозначениях