Файл: Кушнер, Б. А. Лекции по конструктивному математическому анализу.pdf

может быть закодирована следующим образом. Выбе­

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

в А, называется а-системой (а-кортежем, а-вектором)

{0|}; дополнение этого алфавита буквами «—» и «/» по­

алгорифмы. Под «алгорифмом» принято понимать «точ­ ное предписание, определяющее вычислительный про­ цесс, ведущий от варьируемых исходных данных к ис­

в) направленность алгорифма на получение некото­ рого искомого результата, в конце концов и получаемого при надлежащих исходных данных, — результативность алгорифма».

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

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

того или иного точного определения являются и алго­

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

алгорифма понятие нормального алгорифма, предло­

женное А. А. М а р к о в ы м [1]—[2] и специально при­ способленное для оперирования со словами. Следует отметить, что получаемые результаты, по существу, не зависят от принятия или непринятия принципа норма­ лизации. Все построения в конечном счете могут быть

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

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

ствимого построения объекта с требуемым свойством. Традиционная логика разрешает в таких случаях дока­ зывать существование искомого объекта косвенными средствами, например, приведением к противоречию до­ пущения о его несуществовании. Таким образом, тра­ диционная логика пренебрегает различиями суждений вида Эх$(х) и ~~| ~\3х38(х), тогда как конструктивная логика считает эти различия существенными; второе суждение с конструктивной точки зрения, вообще го­ воря, слабее первого. (Мы используем обычные обо­ значения логических связок и кванторов: V —дизъюнк­

ция, & — конъюнкция, =э — импликация, == — эквива­ лентность, ~! — отрицание, V — квантор общности, 3 — квантор существования.) Чтобы подчеркнуть эту новую трактовку существования, мы часто будем употреблять при формулировании экзистенциальных предположений

*) Мнение, что изучение различных объектов может требовать различных логик, высказывалось математиками, придерживающи­