Книги по разным темам Pages:     | 1 |   ...   | 7 | 8 | 9 | 10 | 11 |   ...   | 54 |

Описанное обстоятельство можно рассматривать как универсальное свойство естественных языков, заслуживающее более внимательного рассмотрения. Прежде всего, следует отвергнуть как слишком наивное традиционное объяснение, гласящее, что универсум смыслов естественного языка слишком велик и слишком плохо структурирован и потому не может быть описан с помощью хорошо организованного метаязыка. Проблема в том, что с той же трудностью мы столкнемся, даже если резко ограничим этот универсум Ц - до подмножества арифметики, имеющего дело с маленькими целыми числами. Собственно говоря, именно из-за этой трудности в первую 58 Ч I. М очередь и развилась вся система арифметических обозначений вместе с основными алгоритмами вычислений. Даже словарь элементарной арифметики в естественных языках в основе своей архаичен: конечный натуральный ряд примитивных обществ лодин, два, три, много воспроизводится на экспоненциальной шкале: тысяча, миллион, миллиард, зиллион . Названия даже небольших чисел, например, л 989, являются на самом деле названиями не числа, а его десятичной записи.

Алгебра Виета превосходила полусловесную алгебру Диофанта не потому, что с ее помощью можно было выразить новые значения, но потому, что она была несравненно лучше приспособлена к алгоритмической обработке (лтождественным преобразованиям из нашей школьной алгебры).

Столь характерный для языка науки разрыв интуитивных и эмоциональных связей между текстом и его создателем/пользователем компенсируется приобретаемыми вычислительными автоматизмами.

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

2. Метафора и доказательство Излагаемые здесь взгляды можно рассматривать в связи с обсуждениями школьных и вузовских программ.

В первой половине XX века общее математическое образование было ориентировано на приложения. Оно снабжало учащегося минимумом умений, необходимых для решения повседневных задач и для безболезненного перехода к изучению научных и инженерных Английское слово, означающее примерно лочень-очень много. Ц - Ю. М.

М вычислений в высшей школе. Разрыв между учебными программами и предметом деятельности профессиональных математиков становился все более и более явным. Хорошо известно, что реакцией на этот разрыв была новая математика в США и аналогичные программы в других странах. Эти программы вводили в школьную математику идеи и принципы, позаимствованные у профессионалов:

теорию множеств, доказательства, основанные на аксиомах, культуру строгих определений.

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

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

(в) в математике имеются общепризнанные критерии строгости.

Эти взгляды подвергались широкой критике, например, в книге Джилы Ханны Rigorous Proofs in Mathematics Education (автор: Gila Hanna. Ontario: OISE Press, 983). В частности, автор указывал, что математики далеко не единодушны в том, каковы должны быть критерии строгости (при этом поминалась жаркая полемика между логицистами, формалистами и интуиционистами) и что работающие математики постоянно нарушают все правила.

На мой взгляд, эти возражения Ц - не по существу.

Существенным возражением является то, что упор на доказательства нарушает баланс между базисными ценностями. Доказательство как таковое является производным от идеи истинности. Но существуют ценности и помимо истины: деятельность, красота, понимание;

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

С педагогической точки зрения доказательство Ц - всего лишь один из жанров математического текста. Имеется и множество других жанров: вычисление, набросок доказательства с пояснениями, компьютерная программа, описание алгоритмического языка или такой пренебрегаемый сейчас жанр, как обсуждение связей между формальным определением и интуитивным понятием. У каждого из жанров есть свои законы, и в частности Ц - свои законы строгости; единственная причина, по которой они не кодифицированы, Ц - это то, что им не уделялось специального внимания.

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

Разумеется, это многообразие организовано иерархически. Цели обучения могут варьироваться от приобретения элементарной арифметической и логической грамотности до приобретения программистских навыков и от решения простейших задач из повседневной жизни до овладения принципами современного научного мышления. В спектре этих целей ориентация на строгое доказательство вполне может занимать место на периферии.

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

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

Метафора помогает человеку дышать в этой разреженной атмосфере богов.

Вычислимость и язык. Предисловие Использование электронно-вычислительной техники связано с возможностью алгоритмического решения задач и эффективного вычисления функций. Между тем в математике широко используются функции, заданные неэффективными определениями. Столь же часты доказательства разрешимости задач, например оптимизации, не сопровождаемые алгоритмами их решения.

В действительности класс задач, доступных классическим средствам, в некотором трудно уточняемом смысле строго шире класса задач, решаемых алгоритмически. Книга посвящена прояснению смысла этого утверждения, изложению математических моделей вычислимости, а также некоторых недавних результатов, которые используют понятия теории вычислимости, но выходят за ее пределы. Сюда относятся прежде всего идеи А. Н. Колмогорова о связях понятий вычислимости и случайности, а также результаты о теоретико-числовых аспектах теории вычислений. Более подробно математическая проблематика книги обсуждена во введении. Е 2. Введение. Алгоритм Ц - это текст, который в определенных обстоятельствах может привести к однозначному развитию событий Ц - процессу выполнения алгоритма. Фермент, катализирующий специфическую реакцию, устав караульной службы или программа ЭВМ Ц - примеры алгоритмов в этом широком смысле слова.

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

Предисловие и введение к книге: Вычислимое и невычислимое. М.: Советское радио, 980. С. 5Ц - 5. (Сер. Кибернетика).

62 Ч I. М Таким теоретическим моделям Ц - математической теории алгоритмической вычислимости Ц - посвящена эта книга. Она является естественным продолжением книги Доказуемое и недоказуемое (М.:

Сов. радио, 979), но по большей части может быть прочитана независимо от нее.

2. Простейшая, но очень универсальная модель алгоритма постулирует, что алгоритм предписывает способ вычисления функции, заданной на подмножестве целых положительных чисел Z+ и принимающей целые положительные значения. Для одной и той же функции таких способов может быть много. Оказывается, что среди них есть следующий типовой способ; по любому описанию алгоритма вычисления функции y = f (x) можно построить многочлен Pf (x, y; t1, Е, tn) с целыми коэффициентами такой, что b = f (a), если и только если 0 существуют целые числа t1, Е, tn, Z+ с условием 0 Pf (a, b; t1, Е, tn) = 0.

Зная P1 и a, мы можем найти b = f (a) перебором векторов (b, t1, Е Е, tn) по очереди. Это Ц - основной результат первых двух глав книги.

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

Вторая половина пути состоит в математической обработке понятия рекурсивной функции средствами элементарной, но очень нетривиальной теории чисел. Первые идеи здесь были заложены в работах Г Дэйвиса, Патнэма, Дж. Робинсон, а завершающий результат еделя, получен Ю. В. Матиясевичем.

3. Реальный процесс вычислений производится над записями чисел, скажем, в двоичной системе. Первый этап работы любой большой ЭВМ состоит в алгоритмической переработке программы, написанной на языке программирования, в программу на языке машинных В команд. Осуществляющий такую переработку транслятор есть алгоритм, переводящий символьную информацию в символьную. Поэтому в математической теории вычислимости, опирающейся на понятие рекурсивной функции, должна найти свое место модель связи между числами и текстами. Такой модели Ц - нумерации Г Ц - еделя посвящена гл. IV. Ее основной результат состоит в том, что все элементарные операции над текстом, которые могут лечь в основу процессов алгоритмической переработки текстов, превращаются в рекурсивные функции при любой естественной нумерации текстов. Поэтому нумерация позволяет перевести такую теорию на язык рекурсивных функций.

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

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

Теорема Матиясевича из гл. II также немедленно приводит к утверждению о неразрешимости одной из знаменитых проблем Гильберта.

4. Существование алгоритмически неразрешимых задач и формально недоказуемых истин было первым фундаментальным открытием теории вычислимости, если не считать самой системы основных понятий этой теории. Сейчас такого рода результаты продолжают появляться и вызывать интерес: см., например, з6 гл. V, где сформулирована усиленная теорема Рамсея Ц - несложное комбинаторное утверждение, невыводимость которого из аксиом арифметики была обнаружена лишь в 977 году. Но основные тенденции теории вычислимости определяются работами, которые мотивированы ее прикладными, общематематическими и даже общенаучными аспектами.

К первому направлению относятся многочисленные работы по созданию эффективных, т. е. укладывающихся в реальные ограничения на время работы и объем памяти, алгоритмов решения конкретных вычислительных задач и теории алгоритмов. Сюда же относятся 64 Ч I. М разработки языков программирования и трансляторов, а также принципов их создания. Возникающая новая дисциплина Ц - теоретическое программирование Ц - вынуждена при этом работать иногда на самом краю пропасти неразрешимости, но все же ее главная забота состоит в том, как сделать хорошо то, что в принципе сделать можно.

Цели и объем этой книги не позволили нам коснуться этой огромной и важной области. Теория рекурсивных функций лишь очерчивает ее самые отдаленные границы.

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

Pages:     | 1 |   ...   | 7 | 8 | 9 | 10 | 11 |   ...   | 54 |    Книги по разным темам