LINEBURG


страница 1
(всего 3)

ОГЛАВЛЕНИЕ

След. стр. >>

Библиотека
«Математическое просвещение»




А. Л. Семёнов

МАТЕМАТИКА
ТЕКСТОВ




Издательство Московского центра
непрерывного математического образования
Москва • 2002
Н а у ч н о - р е д а к ц и о н н ы й с о в е т с е р и и:
В. В. Прасолов, А. Б. Сосинский,
В. М. Тихомиров (гл. ред.), И. В. Ященко.



Серия основана в 1999 году.
Библиотека
«Математическое просвещение»
Выпуск 22




А. Л. Семёнов




МАТЕМАТИКА
ТЕКСТОВ




Издательство Московского центра
непрерывного математического образования
Москва • 2002
УДК 510.5/.6
ББК 22.12
С30



Аннотация
В брошюре рассматриваются идеи и конструкции,
лежащие в основе «математики текстов»; среди примеров
её результатов — несчётность множества последовательно-
стей из нулей и единиц, невозможность создать программу,
распознающую самоприменимость программ. Обсуждает-
ся важное понятие сложности текста по Колмогорову,
позволяющее отличать случайные тексты от неслучайных.
Текст брошюры представляет собой обработанную за-
пись лекции, прочитанной автором 5 декабря 1999 года
для участников III Международного математического тур-
нира старшеклассников «Кубок памяти А. Н. Колмогоро-
ва» — школьников 8—11 классов. (Запись Е. Н. Осьмовой,
обработка Р. М. Кузнеца.)
Для широкого круга читателей, интересующихся ма-
тематикой: школьников старших классов, студентов млад-
ших курсов, учителей...


Издание осуществлено при поддержке
Московской городской Думы
и Московского комитета образования.




ISBN 5-94057-006-2

Семёнов Алексей Львович.
Математика текстов.
(Серия: «Библиотека „Математическое просвещение“»).
М.: МЦНМО, 2002. — 16 с.: ил.
Редактор М. П. Каленков. Техн. редактор М. Ю. Панов.

Лицензия ИД № 01335 от 24/III 2000 года. Подписано к печати 4/X 2002 года.
Формат бумаги 60 88 116 .
/ Офсетная бумага № 1. Офсетная печать.
Физ. печ. л. 1,00. Усл. печ. л. 0,98. Уч.-изд. л. 1,15. Тираж ?000 экз. Заказ ????.

Издательство Московского центра непрерывного математического образования.
119002, Москва, Г-2, Бол. Власьевский пер., 11. Тел. 241 05 00.

Отпечатано в ФГУП «Производственно-издательский комбинат ВИНИТИ».
140010, г. Люберцы Московской обл., Октябрьский пр-т, 403. Тел. 554 21 86.
Когда-то в детской энциклопедии я прочитал, что математика —
это наука о числах и фигурах. «Числа и фигуры» — это название заме-
чательной книжки о разных разделах математики, с которой и вам
стоит познакомиться. Однако позже я понял, что в математике есть
много такого, что можно только условно назвать числами или фигура-
ми, например топологические пространства и абстрактные алгебры.
Ещё в восьмом классе я побывал на лекции Андрея Андреевича
Маркова для участников олимпиады и узнал, что можно строить всю
математику, начиная с представления о текстах — последователь-
ностях (цепочках) символов.
Впрочем, название «математика текстов» нетрадиционно,
обычно употребляется название «математическая логика и теория
алгоритмов». Вам, наверное, даже более знаком термин «информа-
тика»: почти во всех школах есть предмет с таким названием. На
уроках информатики в школе проходят разные вещи: так, если в
школе есть компьютерный класс, то детей учат работать с компьюте-
ром. Но я употребил слово «информатика» в другом смысле. Наука,
которую можно назвать также «математическая информатика»
или «теоретическая информатика», в школьном курсе информати-
ки изучается, но совсем немного. (Когда-то я участвовал в написании
первого в нашей стране учебника по информатике для всех школь-
ников 10 и 11 классов, и мы включили в него немного математики.
Так происходит и сейчас. Но часто математику там трудно увидеть,
и требуется некоторое усилие, чтобы понять, где же математическая
суть в этой информатике.) Но всё это: математика текстов, математи-
ческая логика и теория алгоритмов, математическая информатика —
относится к одной и той же области математики.
Математика текстов, в частности математика математических
текстов (для этой математики ещё придумали название «метамате-
матика»), появилась раньше, чем компьютеры, она существовала
ещё в прошлом веке. Необходимость и полезность этой науки хоро-
шо осознавал один из величайших математиков конца XIX — нача-
ла XX века Давид Гильберт. Но именно с возникновением компьюте-
ров математика текстов стала особенно важной областью математики.
Метаматематика изучает, в частности, устройство доказательств
и аксиоматических систем в различных разделах математики, таких
как арифметика, геометрия, теория множеств: что в этих системах
можно доказать, чего доказать невозможно и т. д. Но в этой брошюре
речь пойдёт о более понятных и наглядных вещах.
Начнём с нескольких примеров.
ЛОГИЧЕСКИЕ ПАРАДОКСЫ
Возьмём, например, такой простой текст:
Утверждение, записанное в последней и предпоследней
строках на третьей странице этой брошюры, ложно.
3
Многие из вас, наверное, встречали в тех или иных книжках похо-
жий текст. Напомню, что проблема (кстати вполне математическая)
состоит в том, чтобы понять, истинно это утверждение или ложно.
Подумайте над этим.

Вот ещё один пример.
Некоторые русские слова и словосочетания описывают числа (на-
пример «сто двадцать восемь», «миллион» и т. п.). Рассмотрим такое
число:
наименьшее натуральное число, которое нельзя
(1)
описать текстом короче 100 символов
(символами мы считаем буквы русского языка, цифры, знаки препи-
нания, пробелы).
С одной стороны, ясно, что существуют числа, которые нельзя
описать текстом короче 100 символов — просто потому, что таких
текстов конечное число, а чисел бесконечно много. С другой сторо-
ны, наименьшее такое число описано текстом (1), в котором меньше
100 символов.

И наконец, ещё один пример.
Однажды учитель математики объявил ученикам, что на следу-
ющей неделе он проведёт контрольную работу. При этом накану-
не контрольной они не будут знать точно, что контрольная завтра.
(Уроки математики проходят каждый день с понедельника по пят-
ницу.)
Ясно, что в пятницу контрольной быть не может: тогда в четверг
вечером школьники точно будут знать, что контрольная завтра. Но
тогда в среду вечером они точно будут знать, что контрольная в че-
тверг, ведь в пятницу её быть не может. Значит, и в четверг не мо-
жет быть контрольной… Словом, ученики пришли к выводу, что кон-
трольной вообще не будет, и успокоились. А контрольная произошла
в среду.

Не пытаясь сейчас до конца выяснить причину странности, п а-
р а д о к с а л ь н о с т и приведённых примеров, заметим только, что
парадокс возникал при попытке применить в рассуждении конст-
рукцию
«с одной стороны …, с другой стороны …»,
и при этом получались взаимно противоречащие друг другу утвер-
ждения.
Оказывается, эти конструкции могут быть применены к важным
математическим построениям, уже не парадоксальным, хотя часто
и демонстрирующим невозможность чего-то.
4
ДИАГОНАЛЬНЫЙ МЕТОД КАНТОРА
Рассмотрим квадратную таблицу n n клеток, в которой некото-
рые клетки заштрихованы, а остальные клетки — белые. Пусть нам
нужно построить такую строку, которой нет в этой таблице. Давайте
последовательно выпишем в строку клетки, которые в таблице стоят
по диагонали (рис. 1); полученную строку обозначим через d. Стро-
ка d может присутствовать в нашей таблице, а может и не присут-
ствовать. Поменяем в этой строке цвета, т. е. сделаем белые клетки
чёрными, а чёрные — белыми; переделанную таким образом строку
обозначим через d. Вот строки d в нашей таблице точно нет: от первой
строки она отличается первой клеткой, от второй строки — второй
клеткой, …, от n-й строки — n-й клеткой.




d d


Рис. 1


Рассмотрим теперь бесконечную таблицу. Как и раньше, мы
можем построить строку d из клеток, стоящих на диагонали (только
теперь она получится бесконечной), и получить из неё строку d
(рис. 2). Так же, как в конечном случае, доказывается, что бесконеч-
ной строки, совпадающей с d, в таблице нет.



… …
d d















Рис. 2


Что же в нашей конструкции замечательного? Да, мы научились
строить бесконечную строку, которой нет в нашей таблице. (Такое
построение и называется диагональным.) Какие из этого можно из-
влечь следствия? Самое знаменитое из них получится, если мы пред-
положим, что в нашей таблице имеются вообще в с е бесконечные
строки. В этом случае наше построение сразу приводит к ложности
такого предположения.
5
Мы установили следующий замечательный
Факт. Невозможно в с е бесконечные последовательности из ну-
лей и единиц выписать в таблицу.
Иными словами, все такие последовательности нельзя пересчи-
тать, перенумеровать, решить, какая последовательность будет пер-
вой строкой в нашей таблице, какая — второй и т. д. Говоря науч-
но, невозможно установить взаимно однозначное соответствие меж-
ду натуральными числами и всеми последовательностями из нулей
и единиц.
Эту знаменитую теорему впервые доказал в XIX веке Георг Кан-
тор, основатель теории множеств.
К о н т р о л ь н ы й в о п р о с. Можно ли выписать в бесконечную
таблицу все строчки, в которых лишь конечное число чёрных кле-
ток, а остальные — белые?

ПРОГРАММЫ
Некоторые тексты, в частности, тексты на русском языке, явля-
ются программами, или алгоритмами, — предписаниями, которые
можно выполнить. То, к чему применяется программа, тоже текст.
Например, алгоритм сложения двух натуральных чисел «столби-
ком» — это следующий текст на русском языке:
1. Запиши два числа друг под другом «столбиком».
2. Если числа различаются по длине, дополни короткое слева
нулями, чтобы их длины сравнялись.
3. Запомни 0 в уме.
4. Рассмотри самую правую пару цифр (по вертикали), которая
ещё не была рассмотрена. Сложи эти две цифры и добавь
то, что в уме. Если сумма меньше 10, напиши её под взятой
парой, запомни в уме 0; если сумма больше или равна 10,
запиши под взятой парой последнюю цифру суммы и запомни
в уме 1.
5. Если все цифры слагаемых рассмотрены и в уме 0, то резуль-
тат уже получен в нижней строке; если все цифры слагаемых
рассмотрены и в уме 1, допиши справа 1 к нижней строке, и
это — результат; если не все цифры слагаемых рассмотре-
ны, перейди к пункту 4.
Применяется эта программа к т е к с т у, который представля-
ет собой два числа, записанные в десятичной системе счисления

Двумя чертами слева выделен материал, над которым читателю рекомендуется
тщательно подумать самостоятельно, прежде чем читать раздел «Решения и коммен-
тарии» (стр. 12).
6
и разделённые запятой и пробелом, например к такому:
4850493897329785961, 29785565428497
Бывают программы, р а с п о з н а ю щ и е некоторое свойство. Та-
кие программы на любом тексте*) дают ответ либо «да», либо «нет».
Например, можно себе представить программу, которая определяет,
просто ли данное число.
Ещё один пример программы:
1. К данному тексту припиши в конце букву «А».
Это очень простая программа, она заканчивает работу на любом тек-
сте всего за один шаг. Бывают программы, которые не заканчивают
работу, как, например, такая:
1. К данному тексту припиши в конце букву «А».
2. Перейди к пункту 1.
Она припишет к тексту букву «А» в конце, потом ещё раз припишет
букву «А», потом ещё раз припишет букву «А» и т. д.
Встречаются и более сложные случаи, когда программа на одних
текстах заканчивает работу, а на других — нет. Если программа П на
тексте Т не заканчивает работу, будем это обозначать так: П(Т) = .
Если же программа П заканчивает работу на тексте Т будем писать:
П(Т) = !.

Самоприменимые программы
Поскольку каждая программа представляет собой текст, то мы
можем запустить её на самой себе, на собственном тексте. Программа
П называется самоприменимой, если П(П) = !. А можно ли по про-
грамме П узнать, является ли она самоприменимой?
Если просто запустить программу П на тексте П, то со временем
может выясниться, что она закончила работу. Но ни в какой конеч-
ный момент времени, если программа всё ещё работает, мы не можем
быть уверены, что она никогда не закончит работать. Ведь может
случиться так, что программа работает несколько суток, решая ка-
кую-нибудь сложную задачу, и это не означает, что она собирается
работать бесконечно долго; может быть, она закончит работу через
месяц, или через миллион лет.
Но может быть, есть какой-то другой способ читая текст програм-
мы понять, что она не кончает работать на самой себе?
Допустим, что существует программа S, которая, получая текст
программы П, распознаёт, является ли П самоприменимой, и даёт

*) Математики говорят о работе «программы н а тексте» вместо более длинного
выражения «программы в применении к тексту».
7
ответ либо «да», либо «нет»*). Тогда мы можем построить програм-
му S, которая, получив на входе программу П, запускает программу S
и, если S(П) = «да», работает бесконечно долго (выполняет какую-ни-
будь бесконечную процедуру, например, бесконечное число раз умно-
жает 0 на 0), а если S(П) = «нет», тоже говорит «нет», т. е. заканчивает
работу. Таким образом, программа S не оканчивает работу на само-
применимых программах и заканчивает — на несамоприменимых.
Заметим, что конструкция здесь тоже «диагональная», как и в
случае таблицы с закрашенными клетками. Только сейчас мы рас-
сматриваем таблицу, в которой и по горизонтали, и по вертикали вы-
писаны в с е программы (точнее все конечные последовательности
символов того языка, на котором мы решили записывать программы
(рис. 3), при этом, если текст не является программой, мы можем счи-
тать, что он просто ничего не делает с исходными данными). В клетки
таблицы мы записываем результат работы программы (стоящей в за-
головке столбца) на исходном тексте (стоящем в заголовке строки).

А Б АА АБ БА ББ В ВАБ …

А АБ «да» А ) р? А А
Б !,7 «да» Б Г ё Б Б
АА у, «нет» АА Ж » АА АА
АБ 3, АБ , —« АБ АБ
БА Ыы «да» БА БА БА
ББ 11 «нет» ББ 2ы3 фщ ББ ББ
В Й «нет» В (1( ч)! В В
ВАБ Т «нет» ВАБ 2Ц1 б00: ВАБ ВАБ





Рис. 3


Если программа S существует, то существует и программа S.
Предположим, что S(S) = !, т. е. S кончает работу. Но тогда S(S) = «нет»
по определению S, следовательно, S несамоприменима. И наоборот,
если S(S) = , то S(S) = «да» и S самоприменима. Противоречие.

*) Можно рассмотреть и более сложную программу, которая получает два текста:
программу П и произвольный текст X — и определяет, заканчивает ли П работу на X.
Но о программах, которые применяются к парам текстов — чуть позже.
8
Итак, мы установили следующий
Факт. Не существует программы, которая распознавала бы само-
применимые программы.
Это один из фундаментальных фактов теории алгоритмов, а кон-
струкция, на которой основано его доказательство, — одна из важ-
нейших в этой теории.
Конечно, вопрос о самоприменимости программ кажется доволь-
но экзотическим: не так уж часто мы применяем программу к самой
себе. А вот применение программы к другой программе — обычное
дело: операционная система всякого реального компьютера (а она,
конечно, является программой) выполняет другие программы, задан-
ные человеком, т. е. применяется к ним.
Заметим, что и примеры, приводимые ранее, когда не удава-
лось определить истинность простого на вид утверждения, выглядят
«далёкими от жизни», и неясно, стоит ли им придавать серьёзное
значение. Попробуем объяснить, почему дело обстоит серьёзно. Пер-
вая причина состоит в том, что один контрпример — в математике
уже опровержение общей теории или метода. Вторая причина в том,
что как-то отделить «диагональные» случаи от «недиагональных» не
удаётся, и это может быть доказано после соответствующего уточне-
ния понятий. Однако во многих случаях и математики спрашивают
друг друга: «А есть ли „естественный“ недиагональный пример?».

Универсальная программа
Иногда возникает необходимость в программах, которые приме-
няются к парам текстов. Каким образом можно из пары текстов сде-

страница 1
(всего 3)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign