WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 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 года.

1 Формат бумаги 60 88 /. Офсетная бумага № 1. Офсетная печать.

16 Физ. печ. л. 1,00. Усл. печ. л. 0,98. Уч.-изд. л. 1,15. Тираж000 экз. Заказ.

Издательство Московского центра непрерывного математического образования.

119002, Москва, Г-2, Бол. Власьевский пер., 11. Тел. 241 05 00.

Отпечатано в ФГУП «Производственно-издательский комбинат ВИНИТИ».

140010, г. Люберцы Московской обл., Октябрьский пр-т, 403. Тел. 554 21 86.

Когда-то в детской энциклопедии я прочитал, что математика — это наука о числах и фигурах. «Числа и фигуры» — это название замечательной книжки о разных разделах математики, с которой и вам стоит познакомиться. Однако позже я понял, что в математике есть много такого, что можно только условно назвать числами или фигурами, например топологические пространства и абстрактные алгебры.

Ещё в восьмом классе я побывал на лекции Андрея Андреевича Маркова для участников олимпиады и узнал, что можно строить всю математику, начиная с представления о текстах — последовательностях (цепочках) символов.

Впрочем, название «математика текстов» нетрадиционно, обычно употребляется название «математическая логика и теория алгоритмов». Вам, наверное, даже более знаком термин «информатика»: почти во всех школах есть предмет с таким названием. На уроках информатики в школе проходят разные вещи: так, если в школе есть компьютерный класс, то детей учат работать с компьютером. Но я употребил слово «информатика» в другом смысле. Наука, которую можно назвать также «математическая информатика» или «теоретическая информатика», в школьном курсе информатики изучается, но совсем немного. (Когда-то я участвовал в написании первого в нашей стране учебника по информатике для всех школьников 10 и 11 классов, и мы включили в него немного математики.

Так происходит и сейчас. Но часто математику там трудно увидеть, и требуется некоторое усилие, чтобы понять, где же математическая суть в этой информатике.) Но всё это: математика текстов, математическая логика и теория алгоритмов, математическая информатика — относится к одной и той же области математики.

Математика текстов, в частности математика математических текстов (для этой математики ещё придумали название «метаматематика»), появилась раньше, чем компьютеры, она существовала ещё в прошлом веке. Необходимость и полезность этой науки хорошо осознавал один из величайших математиков конца XIX — начала XX века Давид Гильберт. Но именно с возникновением компьютеров математика текстов стала особенно важной областью математики.

Метаматематика изучает, в частности, устройство доказательств и аксиоматических систем в различных разделах математики, таких как арифметика, геометрия, теория множеств: что в этих системах можно доказать, чего доказать невозможно и т. д. Но в этой брошюре речь пойдёт о более понятных и наглядных вещах.

Начнём с нескольких примеров.

ЛОГИЧЕСКИЕ ПАРАДОКСЫ Возьмём, например, такой простой текст:

Утверждение, записанное в последней и предпоследней строках на третьей странице этой брошюры, ложно.

Многие из вас, наверное, встречали в тех или иных книжках похожий текст. Напомню, что проблема (кстати вполне математическая) состоит в том, чтобы понять, истинно это утверждение или ложно.

Подумайте над этим.

Вот ещё один пример.

Некоторые русские слова и словосочетания описывают числа (например «сто двадцать восемь», «миллион» и т. п.). Рассмотрим такое число:

наименьшее натуральное число, которое нельзя (1) описать текстом короче 100 символов (символами мы считаем буквы русского языка, цифры, знаки препинания, пробелы).

С одной стороны, ясно, что существуют числа, которые нельзя описать текстом короче 100 символов — просто потому, что таких текстов конечное число, а чисел бесконечно много. С другой стороны, наименьшее такое число описано текстом (1), в котором меньше 100 символов.



И наконец, ещё один пример.

Однажды учитель математики объявил ученикам, что на следующей неделе он проведёт контрольную работу. При этом накануне контрольной они не будут знать точно, что контрольная завтра.

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

Не пытаясь сейчас до конца выяснить причину странности, п ар а д о к с а л ь н о с т и приведённых примеров, заметим только, что парадокс возникал при попытке применить в рассуждении конструкцию «с одной стороны …, с другой стороны …», и при этом получались взаимно противоречащие друг другу утверждения.

Оказывается, эти конструкции могут быть применены к важным математическим построениям, уже не парадоксальным, хотя часто и демонстрирующим невозможность чего-то.

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

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

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

… … … Мы установили следующий замечательный Факт. Невозможно в с е бесконечные последовательности из нулей и единиц выписать в таблицу.

Иными словами, все такие последовательности нельзя пересчитать, перенумеровать, решить, какая последовательность будет первой строкой в нашей таблице, какая — второй и т. д. Говоря научно, невозможно установить взаимно однозначное соответствие между натуральными числами и всеми последовательностями из нулей иединиц.

Эту знаменитую теорему впервые доказал в XIX веке Георг Кантор, основатель теории множеств.

К о н т р о л ь н ы й в о п р о с. Можно ли выписать в бесконечную таблицу все строчки, в которых лишь конечное число чёрных клеток, а остальные — белые ПРОГРАММЫ Некоторые тексты, в частности, тексты на русском языке, являются программами, или алгоритмами, — предписаниями, которые можно выполнить. То, к чему применяется программа, тоже текст.

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

1. Запиши два числа друг под другом «столбиком».

2. Если числа различаются по длине, дополни короткое слева нулями, чтобы их длины сравнялись.

3. Запомни 0 в уме.

4. Рассмотри самую правую пару цифр (по вертикали), которая ещё не была рассмотрена. Сложи эти две цифры и добавь то, что в уме. Если сумма меньше 10, напиши её под взятой парой, запомни в уме 0; если сумма больше или равна 10, запиши под взятой парой последнюю цифру суммы и запомни в уме 1.

5. Если все цифры слагаемых рассмотрены и в уме 0, то результат уже получен в нижней строке; если все цифры слагаемых рассмотреныи в уме 1, допиши справа 1 к нижней строке, и это — результат; если не все цифры слагаемых рассмотрены, перейди к пункту 4.

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

и разделённые запятой и пробелом, например к такому:

4850493897329785961, Бывают программы, р а с п о з н а ю щ и е некоторое свойство. Такие программы на любом тексте*) дают ответ либо «да», либо «нет».

Например, можно себе представить программу, которая определяет, просто ли данное число.

Ещё один пример программы:

1. К данному тексту припиши в конце букву «А».

Это очень простая программа, она заканчивает работу на любом тексте всего за один шаг. Бывают программы, которые не заканчивают работу, как, например, такая:

1. К данному тексту припиши в конце букву «А».

2. Перейди к пункту 1.

Она припишет к тексту букву «А» в конце, потом ещё раз припишет букву «А», потом ещё раз припишет букву «А» ит. д.





Встречаются и более сложные случаи, когда программа на одних текстах заканчивает работу, а на других — нет. Если программа П на тексте Т не заканчивает работу, будем это обозначать так: П(Т)=.

Если же программа П заканчивает работу на тексте Т будем писать:

П(Т)=!.

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

Но может быть, есть какой-то другой способ читая текст программы понять, что она не кончает работать на самой себе Допустим, что существует программа S, которая, получая текст программы П, распознаёт, является ли П самоприменимой, и даёт *) Математики говорят о работе «программы н а тексте» вместо более длинного выражения «программы в применении к тексту».

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

Заметим, что конструкция здесь тоже «диагональная», как и в случае таблицы с закрашенными клетками. Только сейчас мы рассматриваем таблицу, в которой и по горизонтали, и по вертикали выписаны в с е программы (точнее все конечные последовательности символов того языка, на котором мы решили записывать программы (рис. 3), при этом, если текст не является программой, мы можем считать, что он просто ничего не делает с исходными данными). В клетки таблицы мы записываем результат работы программы (стоящей в заголовке столбца) на исходном тексте (стоящем в заголовке строки).

А Б АА АБ БА ББ В ВАБ … А АБ «да» А ) р А А Б !,7 «да» Б Г ё Б Б АА у, «нет» АА Ж » АА АА АБ 3, АБ, —« АБ АБ БА Ыы «да» БА БА БА ББ 1 1 «нет» ББ 2ы3 фщ ББ ББ В Й «нет» В (1( ч)! В В ВАБ Т «нет» ВАБ 2Ц1 б00: ВАБ ВАБ Рис. Если программа S существует, то существует и программа S.

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

*) Можно рассмотреть и более сложную программу, которая получает два текста:

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

Но о программах, которые применяются к парам текстов — чуть позже.

… Итак, мы установили следующий Факт. Не существует программы, которая распознавала бы самоприменимые программы.

Это один из фундаментальных фактов теории алгоритмов, а конструкция, на которой основано его доказательство, — одна из важнейших в этой теории.

Конечно, вопрос о самоприменимости программ кажется довольно экзотическим: не так ужчасто мы применяем программу к самой себе. А вот применение программы к другой программе — обычное дело: операционная система всякого реального компьютера (а она, конечно, является программой) выполняет другие программы, заданные человеком, т. е. применяется к ним.

Заметим, что и примеры, приводимые ранее, когда не удавалось определить истинность простого на вид утверждения, выглядят «далёкими от жизни», и неясно, стоит ли им придавать серьёзное значение. Попробуем объяснить, почему дело обстоит серьёзно. Первая причина состоит в том, что один контрпример — в математике уже опровержение общей теории или метода. Вторая причина в том, что как-то отделить «диагональные» случаи от «недиагональных» не удаётся, и это может быть доказано после соответствующего уточнения понятий. Однако во многих случаях и математики спрашивают друг друга: «А есть ли „естественный“ недиагональный пример».

Универсальная программа Иногда возникает необходимость в программах, которые применяются к парам текстов. Каким образом можно из пары текстов сделать один Записать два текста рядом, один за другим К сожалению, после этого уже невозможно будет определить, где кончается первый текст и начинается второй. Чередовать буквы первого и второго текста Но, если тексты разной длины, снова не удастся разделить полученный текст на два исходных*).

Попробуем теперь применить более сложный приём. Запишем первый текст, удваивая каждую его букву. Например, текст Универсальная программа (знак обозначает пробел) запишется так:

УУннииввееррссааллььннааяя ппррооггррааммммаа После первого текста запишем разделитель «аб». Потом запишем второй текст без изменений. Допустим, что второй текст выглядит так:

Сложность текста *) Вспомним, когда в алгоритме сложения «столбиком» мы из пары чисел делали один текст для работы программы на нём, мы использовали разделитель «, » —запятую и пробел, но это было возможно, поскольку в записи самих чисел эти два символа встречаться не могли.

Тогда окончательный результат будет таким:

Pages:     || 2 | 3 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.