Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 44

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 44)

Здесь впервые стоит упомянуть (пока неформально) два 'понятия, о которых подробнее будет говориться в двух следующих главах, — синтаксис и семантика. Синтаксические свойства алгоритма — это свойства описывающих его текстов, т. е. свойства конечных слов в фиксированном алфавите. Семантические (илн смысловые) свойства алгоритмов связаны с тем, что ов делает; их естественно описывать в терминах функций и классов эквивалентности функций, вычисляемых алгоритмами. Хорошо известно, что в процессе отладки программ синтаксические ошибки отыскиваются довольно быстро1 все неприятности связаны с анализом семантики неотлаженной программы, т. е с попытками установить, что же она делает вместо того, чтобы делать задуманное.

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

Например, в гл. 3 рассматривались алгоритмы распознавания свойств логических функций, описанных на языке формул в различных базисах. до сих пор речь шла о неразрешимых пробдемах внутри самой теории алгоритмов. Некоторые нз ннх, такие как проблема остановки или теорема Райса, имеют вполне реальную интерпретацию в практике программирования. Неразрешимости возникают и в других областях: в теории автоматов, в теории языков и грамматик (см.

гл. 7) и т.д. Постепенно они становятся бытом дискретной математики, и с их существованием приходится считаться, С теоретической точки зрения, неразрешимость — не неудача, а науч. ный факт, Знание основных неразрешимостей теории алгоритмов должно быть для специалиста по дискретной мате. 214 матике таким же элементом научной культуры, как для физика — знание о невозможности вечного двигателя.

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

Поэтому, если проблема неразрешима, надо искать ее разрешимые частные случаи. Во-вторых, появление неразрешимости — это, как правило, результат чрезмерной общности задачи (или языка, па котором описаны объекты задачи). Задача в более общей постановке имеет больше шансов оказаться неразрешимой. ГЛЛВЛ ШБСТЛЯ ФОРМАЛЬНЫЕ СИСТЕМЫ Формальные системы — это системы операций над объектами, понимаемыми как последовательности символов (т. е.

как слова в фиксированных алфавИтах); сами операции также являются операциями над символами. Термин «формальный» подчеркивает, что обьекты и операции над ними рассматриваются чисто формально, без каких бы то нн было содерхгательных интерпретаций символов. Предполагается, что между. символами не существует никаких связей и отношений, кроме тех, которые явно описаны средствами самой формальной системы. Если предложить читателю упорядочить объекты 53, !09, 3, то, скорее всего, он без всяких дополнительных вопросов расположит их в порядке 3, 53, 109.

Иначе говоря, этой задаче будет дана обычная арифметическая интерпретация: последовательности цифр рассматриваются как изображения чисел в десятичной системе, упорядочение этих последовательностей есть расположение изображаемых ими чисел по возрастанию, а правила сравнения таких изображений чисел известны настолько хорошо, что обычно о них никто не задумывается. В действительности же такое истолкование задачи, вообще говоря, не вытекает из текста «упо. рядочить объекты 53, 109, 3»; его можно понимать как задачу лексико-графического упорядочения (что приведет к результату 109, 3, 53), как задачу распределения бегунов 215 с номерами 53, 109, 3 по дорожкам (решение которой зависит от процедуры распределения и заведомо не связано с числовой интерпретацией объектов) и т.

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

Сходные соображения по поводу того, что такое «точное описание», довольно подробно рассматривались при обсуждении понятия «алгоритм» и таких его элементов, как «данные», «элементарный шаг» ($5.1), а также в связи с понятием «финитного подхода» к математике (конец $3.4). В определенном смысле проблему точного описания некоторого множества можно рассматривать как проблему построения алгоритма, перечисляющего или порождающего это множе'ство. Однако иногда акценты здесь несколько смещаются. Чтобы было ясно, о чем идет речь, рассмотрим формализацию понятия формулы (см.

гл. 3 и далее $ 6.1, 6.2), которая дается индуктивным определением формулы. Нетрудно показать, что множество формул, определенных таким образом, перечислимо (и даже разрешимо) и, следовательно, существует алгоритм, порождающий это множество. Однако конкретный порядок порождения формул, который определил бы номер формулы в списке этих формул, т. е. конкретный перечисляющий алгоритм, этим определением не фиксируется. Зафиксировать такой алгоритм можно различными способами, но для точного определения формулы этого не требуется.

Индуктивное определение формулы — простой пример описания перечислимого множества, в котором использованы все существенные составные части понятия «алгоритм», кроме одного — детерминированности. Отбрасывая несущественный здесь порядок перечисления элементов множества, мы выигрываем в компактности описания, которое при этом не становится менее точным. Такое описание, не являясь алгоритмом, представляет собой формальную систему, однозначно описывающую множество формул.

Исторически теория формальных систем, так же как 216 и теория алгоритмов, возникла в рамках оснований математики при исследовании строения аксиоматических теорий и методов доказательства в таких теориях. С их изучения и начнется знакомство с формальными системами. 6.1. ФОРМАЛЬНЫЕ ТЕОРИИ (ЛОГИЧЕСКИЕ ИСЧИСЛЕНИЯ) ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИИ Принципы построения формальных теорий. Всякая точная теория определяется, во-первых, языком„т.е.

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

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

Известно, например, что основания дифференциального и интегрального исчислений, разработанных в ХЪ"111 в. Ньютоном и Лейбницем, в Х!Х в. подверглись серьезному пересмотру; математический анализ в его современном виде опирается на работы Коши, Больцано, Вейерштрасса по теории пределов.

В конце Х1Х в. такой пересмотр затронул общие принципы организации математических теорий. Это привело к созданию новой отрасли математики — оснований математики, предметом которой стало как раз строение математических утверждений и теорий и которая поставила своей целью ответить на вопросы типа; «как должна быть построена теория, чтобы в ней не возникало противоречий?», «какими свойствами должны обладать методы доказательств, чтобы считаться достаточно строгими?» и т. д.

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

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

2. Выделяется подмножество формул, называемых аксиомами теории. Множество может быть и бесконечным; во всяком случае оно должно быть разрешимо. 3. Задаются правила вывода теории. Правило вывода м(Рь ..., Р», 6) — зто вычнслимое отношение на множестве формул. Если формулы Рь ..., Р„, 6 находятся в отношении Й, то формула 6 называется непосредственно выводимой нз Рь ..., Р, по правилу й. Часто правило 1т(Ри ..., Р„, 6) записывается в виде " '" ' " . Формулы Рь, Р, называР1 ° ° ° Рп ются посылками правила К, а 6 — его следствием или за-.

Характеристики

Список файлов книги