Текст книги "Большая Советская Энциклопедия (АЛ)"
Автор книги: Большая Советская Энциклопедия
Жанр:
Энциклопедии
сообщить о нарушении
Текущая страница: 8 (всего у книги 44 страниц)
Алгебраическая геометрия
Алгебраи'ческая геоме'трия, раздел математики, изучающий алгебраические многообразия. Так называются множества точек в n-мерном пространстве, координаты которых (x1 , x2 ,...,xn ) являются решениями системы уравнений:
F1 (X1 , Х2 ..., Xn ) = 0,
Fm (X1 , x2 , ..., Xn ) = 0,
где Fi ,..., Fm– многочлены от неизвестных x1 , ..., xn . Каждое алгебраическое многообразие имеет определённую размерность, которая является числом независимых параметров, определяющих точку на многообразии. Алгебраические многообразия, имеющие размерность 1, называются алгебраическими кривыми, имеющие размерность 2 – алгебраическими поверхностями. Примерами алгебраических кривых могут служить конические сечения .
Два алгебраических многообразия называются бирационально эквивалентными, если координаты каждой точки одного многообразия выражаются при помощи рациональных функций через координаты точки другого многообразия, и наоборот. В А. г. алгебраические многообразия обычно изучаются с точностью до бирациональной эквивалентности, поэтому одной из основных задач А. г. является построение бирациональных инвариантов для алгебраических многообразий. Наиболее важные из известных бирациональных инвариантов строятся с помощью средств математического анализа (т. н. трансцендентных методов), в особенности при помощи кратных интегралов по алгебраическому многообразию. Кроме трансцендентных методов, в А. г. часто применяются геометрические методы проективной геометрии , а также топологические методы (см. Топология ). Последнее вызвано тем, что некоторые важные бирациональные инварианты, например род кривой (см. ниже), алгебраических многообразий носят топологический характер. Особенно большую роль играет связь А. г. с топологией в свете теоремы японского математика Хиронака, согласно которой всякое алгебраическое многообразие бирационально эквивалентно многообразию, не имеющему особых точек.
Наиболее разработанная часть А. г. – теория алгебраических кривых. Основным бирациональным инвариантом алгебраической кривой является её род. Если алгебраическая кривая плоская, т. е. задаётся в декартовых координатах уравнением F(х, у) = 0, то род кривой g = (m – 1)(m – 2)/2 – d, где m — порядок кривой, а d — число её двойных точек. Род кривой всегда есть целое неотрицательное число. Кривые рода нуль бирационально эквивалентны прямым, т. е. параметрически могут быть заданы при помощи рациональных выражений. Кривые рода 1 могут быть параметризованы эллиптическими функциями и поэтому называются эллиптическими кривыми. Кривые рода больше 1 могут быть параметризованы с помощью автоморфных функций . Каждая кривая рода g, большего 1, с точностью до бирациональной эквивалентности однозначно определяется 3g – 3 комплексными параметрами, которые сами пробегают некоторое алгебраическое многообразие.
В многомерном случае наиболее изученный класс алгебраических многообразий образуют абелевы многообразия. Это – замкнутые подмногообразия проективного пространства, являющиеся одновременно группами , причём так, что умножение задаётся рациональными выражениями. Умножение на таком многообразии автоматически оказывается коммутативным. Алгебраическая кривая является абелевым многообразием тогда и только тогда, когда она имеет род 1, т. е. является эллиптической кривой.
Теория алгебраических кривых и теория абелевых многообразий тесно связаны между собой. Всякая алгебраическая кривая рода, большего 0, канонически погружается в некоторое абелево многообразие, называемое якобиевым многообразием для данной кривой. Якобиево многообразие является важным инвариантом кривой и почти полностью определяет самоё кривую.
Исторически А. г. возникла из изучения кривых и поверхностей низких порядков. Классификация кривых третьего порядка была дана И. Ньютоном (1704). В 19 в. А. г. постепенно переходит от изучения специальных классов кривых и поверхностей к постановке общих проблем, относящихся ко всем многообразиям. Общая А. г. была построена в конце 19 и начале 20 вв. в трудах немецкого математика М. Нётера, итальянских математиков Ф. Энрикеса, Ф. Севери и др. Своего расцвета А. г. достигает в 20 в. (работы французского математика А. Вейля, американского математика С. Лефшеца и др.). Крупные достижения в А. г. имеют советские математики Н. Г. Чеботарев , И. Г. Петровский , И. Р. Шафаревич .
А. г. является одним из наиболее интенсивно развивающихся разделов математики. Методы А. г. оказывают огромное влияние на такие смежные с А. г. разделы математики, как теория функций многих комплексных переменных, теория чисел, а также на более далёкие от А. г. разделы математики – такие, как уравнения в частных производных, алгебраическая топология, теория групп и др.
Лит.: Ван-дер-Варден Б. Л., Современная алгебра, пер. с нем., [2 изд.], ч. 1—2, М. – Л., 1947; Чеботарев Н. Г., Теория алгебраических функций, М. – Л., 1948; Ходж В., Пидо Д., Методы алгебраической геометрии, пер. с англ., т. 1—3, М., 1954 – 55; Алгебраические поверхности, М., 1965; WeiI A.. Foundations of algebraic géometry, N. Y., 1946.
Б. Б. Венков.
Алгебраическая кривая
Алгебраи'ческая крива'я, кривая, задаваемая в декартовых координатах алгебраическим уравнением. См. Алгебраическая геометрия .
Алгебраическая поверхность
Алгебраи'ческая пове'рхность, поверхность, задаваемая в декартовых координатах алгебраическим уравнением. См. Алгебраическая геометрия .
Алгебраическая функция
Алгебраи'ческая фу'нкция, функция, удовлетворяющая алгебраическому уравнению . А. ф. принадлежат к числу важнейших функций, изучаемых в математике. Из них многочлены и частные многочленов [например,
называются рациональными, а прочие А. ф. – иррациональными. Простейшими примерами последних могут служить А. ф., выражаемые с помощью радикалов [например,
Однако существуют А. ф., которые невозможно выразить через радикалы [например, функция у = f (х ), удовлетворяющая уравнению: y5 + 3ух4 + x5 = 0]. Примерами неалгебраических, т. н. трансцендентных функций , встречающихся в школьном курсе алгебры, являются: степенная xa (если a — иррациональное число), показательная ах, логарифмическая и т. д. Общая теория А. ф. представляет обширную математическую дисциплину, имеющую важные связи с теорией аналитических функций (А. ф. составляют специальный класс аналитических функций), алгеброй и алгебраической геометрией . Самая общая А. ф. многих переменных u = f (x , у , z , ...) определяется как функция, удовлетворяющая уравнению вида:
Ро (х , у , z , ...)un + P1 (x , y , z , ...)un-1 + … +Pn (x , y , z , ...) = 0, (1)
где Р , Р1 , ..., Pn– какие-либо многочлены относительно х , у , z ,... . Всё выражение, стоящее в левой части, представляет некоторый многочлен относительно х , у , z ,... и n . Его можно считать неприводимым, т. е. не разлагающимся в произведение многочленов более низких степеней; кроме того, многочлен P можно считать не равным тождественно нулю. Если n = 1, то u представляет рациональную функцию (u = -P1 /P ), частным случаем которой – целой рациональной функцией – является многочлен (если P = const ¹ 0). При n > 1 получается иррациональная функция; если n = 2, то она выражается через многочлены с помощью квадратного корня; если n = 3 или n = 4, то для u получается выражение, содержащее квадратные и кубические корни.
При n ³ 5 число каких бы то ни было корней из многочленов. Иррациональная А. ф. всегда многозначна, а именно (при наших обозначениях и предположениях) является n -значной аналитической функцией переменных х , у , z ,...
Лит.: Чеботарев Н. Г., Теория алгебраических функций, М. – Л., 1948.
Алгебраическое выражение
Алгебраи'ческое выраже'ние, выражение, составленное из букв и цифр, соединённых знаками действий сложения, вычитания, умножения, деления, возведения в целую степень и извлечения корня (показатели степени и корня должны быть постоянными числами). А. в. называется рациональным относительно некоторых букв, в него входящих, если оно не содержит их под знаком извлечения корня, например
рационально относительно a, b и с. А. в. называется целым относительно некоторых букв, если оно не содержит деления на выражения, содержащие эти буквы, например 3а/с + bc2 – 3ас/4 является целым относительно а и b. Если некоторые из букв (или все) считать переменными, то А. в. есть алгебраическая функция .
Алгебраическое дополнение
Алгебраи'ческое дополне'ние, см. в ст. Определитель .
Алгебраическое уравнение
Алгебраи'ческое уравне'ние, уравнение, получающееся при приравнивании двух алгебраических выражений . А. у. с одним неизвестным называется дробным, если неизвестное входит в знаменатель, и иррациональным, если неизвестное входит под знаком радикала. Всякое А. у. может быть преобразовано без потери корней к виду a xn + a1 xn-1 + ... + an = 0. О решении таких уравнений см. Алгебра и Численное решение уравнений .
Д. К. Фаддеев.
Алгебраическое число
Алгебраи'ческое число', число а, удовлетворяющее алгебраическому уравнению a1 an + ... + акa +an+1 = 0, где n ³ 1, a1 , ..., an , an+1 – целые (рациональные) числа. Число a называется целым А. ч., если a1 = 1. Если многочлен f(x) = a1 xn + ... + an x + an+1 не является произведением двух др. многочленов положительной степени с рациональными коэффициентом, то число n называется степенью А. ч. a. Простейшие А.ч. – корни двучленного уравнения xn = а, где а — рациональное число. Например, А. ч. будут рациональные числа, числа
целыми А. ч. будут целые числа, числа
С понятием А. ч. тесно связаны два больших направления в теории чисел. 1) Арифметика А. ч. (алгебраическая теория чисел), созданная Э. Куммером в середине 19 в., изучает свойства А. ч. Целые А. ч. обладают рядом свойств, аналогичных свойствам целых рациональных чисел, однако теорема об единственности разложения числа на простые множители не имеет места в теории целых А. ч. Для сохранения единственности разложения Куммер ввёл в рассмотрение т. н. «идеальные» числа (см. Идеал ). 2) Теория приближения А. ч. изучает степень приближения А. ч. рациональными числами или алгебраическими же числами. Первым результатом в этом направлении была теорема Ж. Лиувилля , показывающая, что А. ч. «плохо» приближаются рациональными числами, точнее: если a – А. ч. степени n, то при любых целых рациональных р и q имеет место неравенство [a – p/q] > C/qn , где С = С(a) > 0 – постоянная, не зависящая от р и q, отсюда следует, что легко построить произвольное количество неалгебраических – трансцендентных чисел .
Лит.: Гекке Э., Лекции по теории алгебраических чисел, пер. с нем., М. – Л., 1940; Гельфонд А. О., Трансцендентные и алгебраические числа, М., 1952; Боревич З. И., Шафаревич И. P., Теория чисел, М., 1964.
А. А. Карацуба.
Алгебры основная теорема
А'лгебры Основна'я теоре'ма, название теоремы о существовании комплексных корней алгебраического уравнения a xn + a1 xn-1 + ... +an = 0 с комплексными коэффициентами. См. Алгебра .
Алгол
Алго'л, сокращённое название ряда языков программирования . Образовано из начальных букв английских слов algorithmic (алгоритмический) и language (язык). Разработан группой учёных разных стран в 1958—60. Окончательный вид языка, принятый на международной конференции в Париже (январь 1960), получил название «Алгол-60» (в отличие от первоначального вида, названного «Алгол-58»).
Основными символами А. являются десятичные цифры, строчные и заглавные латинские буквы, знаки препинания, знаки математических и логических операций, прочие специальные знаки и некоторые английские слова (в частности, begin и end). Из основных символов в А. по определённым правилам образуются конструкции – числа и выражения (арифметические, логические и др.), описания, примечания и операторы , которые, в свою очередь, в сочетании с основными символами образуют более сложные операторы и т. д. Алгоритм, заданный на А., называется алгол-программой. С помощью специальной программы он преобразуется в программу на языке конкретной цифровой вычислительной машины.
Лит.: Алгоритмический язык АЛГОЛ-60, пер. с англ., М., 1965; Лавров С. С., Универсальный язык программирования (АЛГОЛ-60), 2 изд., М., 1967.
Алголь
Алго'ль, b Персея, затменная переменная звезда, переменность которой открыта в 1669. Блеск А. изменяется от 2,2 до 3,5 визуальной звёздной величины с периодом 2,867 суток. Расстояние от Солнца – 36 парсек. Переменные звёзды с кривой изменения блеска, как у А., составляют класс звёзд типа Алголя.
Алгонкинские языки
Алгонки'нские языки', одна из основных семей языков североамериканских индейцев. В результате истребления племён А. я. сохранились лишь в немногих местах в США и Канаде, главным образом в районе Великих озёр и южнее. Распадаются на 5 основных групп: языки т. н. «черноногих» индейцев; чейенн; арапахо; центральная и восточная группы; калифорнийская группа. Наиболее обширны центральная и восточная группы, к которым относятся языки собственно алгонкинский, оджибве, оттава (в районе озера Верхнего и Гурон), кри (на Лабрадоре), делаварский (в Пенсильвании и в штатах Нью-Йорк и Нью-Джерси), фокс (долина Миссисипи), а также ныне исчезнувшие языки могикан, массачусетский и др. Языки т. н. «черноногих» индейцев (блэкфут) распространены в Канаде, у подножия Скалистых гор и в северной части Монтаны; шейен – в юго-восточной части Миннесоты и северо-восточной части Южной Дакоты; арапахо – в восточной части Северной Дакоты и в южной части Монтаны; калифорнийская группа (Калифорния) представлена двумя языками – вийот и юрок. В грамматическом отношении А. я. характеризуются ярко выраженной инкорпорацией (см. Инкорпорирующие языки ). В А. я. элементы, соответствующие второстепенным членам предложения, зависящие от глагольного сказуемого, входят в состав последнего как морфы, в результате чего одна словоформа соответствует целому предложению.
Лит. :Boas Fr., Handbook of American Indian languages, pt I, Wash., 1911: Pilling J. С., Bibliography of the Algonquian languages. Wash., 1891.
Алгонкины
Алгонки'ны, группа родственных по языку (см. Алгонкинские языки ) индейских племен, древнейших насельников Северной Америки, охотников, рыболовов и ранних земледельцев, живших в прошлом на большом пространстве от Атлантического побережья до Скалистых гор. Территориально различаются 4 группы А.: северо-восточная (кри , монтанье, наскапи , микмаки и др.); приатлантическая (абенаки, наррагансеты, массачусеты, поухатаны и др.), почти полностью уничтоженная на первых же этапах колонизации материка европейцами: центральная (могиканы , делавары , майами, иллинойсы, оттавы, оджибве , шауни , собственно алгонкины, меномини и др.), оставившая о себе память в топонимике; западная («черноногие», чейенны , арапахо , ацина). Остатки алгонкинских племён разбросаны по резервациям США (100 тыс. чел.) и Канады (75 тыс. чел.; 1961). К А. в языковом отношении близки племена Тихоокеанского побережья Северной Америки селиши (численность в США 12 тыс. чел., в Канаде 15 тыс. чел.) и вакаши (в Канаде 6 тыс. чел.).
Лит.: Народы Америки, т. 1, М., 1959.
Ю. П. Аверкиева.
Алгоритм
Алгори'тм, алгорифм, одно из основных понятий (категорий) математики, не обладающих формальным определением в терминах более простых понятий, а абстрагируемых непосредственно из опыта. А. являются, например, известные из начальной школы правила сложения, вычитания, умножения и деления столбиком. Вообще, под А. понимается всякое точное предписание, которое задаёт вычислительный процесс (называемый в этом случае алгоритмическим), начинающийся с произвольного исходного данного (из некоторой совокупности возможных для данного А. исходных данных) и направленный на получение полностью определяемого этим исходным данным результата; например, в упомянутых А. арифметических действий возможными результатами могут быть натуральные числа, записанные в десятичной системе, а возможными исходными данными упорядоченные пары таких чисел, и содержание предписания, т. о., помимо инструкции по развёртыванию алгоритмического процесса, должно входить также: 1) указание совокупности возможных исходных данных (в. и. д.) и 2) правило, по которому процесс признается закончившимся ввиду достижения результата. Не предполагается, что результат будет обязательно получен: процесс применения А. к конкретному в. и. д. (т.е. алгоритмический процесс, развёртывающийся начиная с этого данного) может также оборваться безрезультатно или не закончиться вовсе. В случае, если процесс заканчивается (соответственно не заканчивается) получением результата, говорят, что А. применим (соответственно неприменим) к рассматриваемому в. и. д. (Можно построить такой А. Á, для которого не существует А., распознающего по произвольному возможному для Á исходному данному, применим к нему Á или нет; такой А. Á можно, в частности, построить так, чтобы совокупностью его в. и. д. служил натуральный ряд.)
Понятие А. занимает одно из центральных мест в современной математике, прежде всего вычислительной. Так, проблема численного решения уравнений данного типа сводится к отысканию А., который всякую пару, составленную из произвольного уравнения этого типа и произвольного рационального числа e, перерабатывает в число (или набор чисел) меньше, чем на e, отличающееся (отличающихся) от корня (корней) этого уравнения. Усовершенствование вычислительных машин даёт возможность реализовать на них всё более сложные А. Однако встретившийся в описывающей понятие А. формулировке термин «вычислительный процесс» не следует понимать в узком смысле только цифровых вычислений. Так, уже в школьном курсе алгебры говорят о буквенных вычислениях, да и в арифметических вычислениях появляются отличные от цифр символы: скобки, знак равенства, знаки арифметических действий. Можно пойти дальше и рассматривать вычисления с произвольными символами и их комбинациями; именно таким широким пониманием пользуются при описании понятия А. Так, можно говорить об А. перевода с одного языка на другой, об А. работы поездного диспетчера (перерабатывающего информацию о движении поездов в приказы) и др. примерах алгоритмического описания процессов управления; именно поэтому понятие А. является одним из центральных понятий кибернетики. Вообще, исходными данными и результатами А. могут служить самые разнообразные конструктивные объекты; например, результатами т. н. распознающих А. служат слова «да» и «нет».
Пример алгоритма . В. и. д. и возможными результатами пусть служат всевозможные конечные последовательности букв a и b («слова в алфавите {a, b}»). Условимся называть переход от слова Х к слову Y «допустимым» в следующих двух случаях (ниже Р обозначает произвольное слово): 1) Х имеет вид аР, а Y имеет вид Pb; 2) X имеет вид baP, а Y имеет вид Paba. Формулируется предписание : «взяв какое-либо слово в качестве исходного, делай допустимые переходы до тех пор пока не получится слово вида aaP; тогда остановись, слово Р и есть результат». Это предписание образует А., который обозначим через Â. Возьмем в качестве исходного данного слово babaa. После одного перехода получим baaaba, после второго aabaaba. В силу предписания мы должны остановиться, результат есть baaba. Возьмём в качестве исходного данного слово baaba. Получим последовательно abaaba, baabab, abababa, bababab, babababa, ... Можно доказать, что процесс никогда не кончится (т. е. никогда не возникает слово, начинающееся с aa и для каждого из получающихся слов можно будет совершить допустимый переход). Возьмём теперь в качестве исходного данного слово abaab. Получим baabb, abbaba, bbabab. Далее мы не можем совершить допустимый переход, и в то же время нет сигнала остановки. Произошла т.н. «безрезультативная остановка». Итак, Â применим к слову babaa и неприменим к словам baaba и abaab.
Значение А. А. в науке встречаются на каждом шагу; умение решать задачу «в общем виде"всегда означает, по существу, владение некоторым А. Говоря, например, об умении человека складывать числа, имеют в виду не то, что он для любых двух чисел рано или поздно сумеет найти их сумму, а то, что он владеет некоторым единообразным приёмом сложения, применимым к любым двум конкретным записям чисел, т. е. иными словами, А. сложения (примером такого А. и является известное правило сложения чисел столбиком). Понятие задачи «в общем виде» уточняется при помощи понятия массовая проблема (м. п.). М.п. задаётся серией отдельных, единичных проблем и состоит в требовании найти общий метод (то есть А.) их решения. Так, проблема численного решения уравнений данного типа и проблема автоматического перевода суть м. п.: образующими их единичными проблемами являются в 1-м случае проблемы численного решения отдельных уравнений данного типа, а во 2-м случае – проблемы перевода отдельных фраз. Ролью м. п. и определяется как значение, так и сфера приложения понятия А. М. п. чрезвычайно характерны и важны для математики: например, в алгебре возникают м.п. проверки алгебраических равенств различных типов, в математической логике – м. п. распознавания выводимости предложении из заданных аксиом и т.п. (для математической логики понятие А. существенно ещё и потому, что на него опирается центральное для математической логики понятие исчисления , служащее обобщением и уточнением интуитивных понятий «вывода» и «доказательства»). Установление неразрешимости какой-либо массовой проблемы (например, проблемы распознавания истинности или доказуемости для какого-либо логико-математического языка), т. е. отсутствия единого А., позволяющего найти решения всех единичных проблем данной серии, является важным познавательным актом, показывающим, что для решения конкретных единичных проблем принципиально необходимы специфические для каждой такой проблемы методы. Существование неразрешимых м. п. служит, т. о., проявлением неисчерпаемости процесса познания.
Содержательные явления, которые легли в основу образования понятия «А.», издавна занимали важное место в науке. С древнейших времён многие задачи математики заключались в поисках тех или иных конструктивных методов. Эти поиски, особенно усилившиеся в связи с созданием удобной символики, а также осмысления принципиального отсутствия искомых методов в ряде случаев (задача о квадратуре круга и подобные ей) – все это было мощным фактором развития научных знаний. Осознание невозможности решить задачу прямым вычислением привело к созданию в 19 в. теоретико-множественной концепции . Лишь после периода бурного развития этой концепции (в рамках которой вопрос о конструктивных методах в современном их понимании вообще не возникает) оказалось возможным в середине 20 в вновь вернуться к вопросам конструктивности, но уже на новом уровне, обогащенном выкристаллизовавшимся понятием А. Это понятие легло в основу особого конструктивного направления в математике.
Само слово «А.» происходит от algorithmi, являющегося, в свою очередь, латинской транслитерацией арабского имени хорезмийского математика 9 в. аль-Хорезми . В средневековой Европе А. называется десятичная позиционная система счисления и искусство счёта в ней, поскольку именно благодаря латинскому переводу (12 в.) трактата аль-Хорезми Европа познакомилась с позиционной системой.
Строение алгоритмического процесса. Алгоритмический процесс есть процесс последовательного преобразования конструктивных объектов (к. о.), происходящий дискретными «шагами»; каждый шаг состоит в смене одного к. о. другим. Так, при применении А. Ã к слову baaba возникают последовательно baaba, abaaba, baabab и т. д. А при применении, скажем, А. вычитания столбиком к паре <307, 49> последовательно возникнут такие к. о.:
При этом в ряду сменяющих друг друга к. о. каждый последующий полностью определяется (в рамках данного А.) непосредственно предшествующим. При более строгом подходе предполагается также, что переход от каждого к. о. к непосредственно следующему достаточно «элементарен» – в том смысле, что происходящее за один шаг преобразование предыдущего к. о. в следующий носит локальный характер (преобразованию подвергается не весь к. о., а лишь некоторая, заранее ограниченная для данного А. его часть и само это преобразование определяется не всем предыдущим к. о., а лишь этой ограниченной частью).
Т. о., наряду с совокупностями возможных исходных данных и возможных результатов, для каждого А. имеется ещё совокупность промежуточных результатов (п. р.), представляющая собой ту рабочую среду, в которой развивается алгоритмический процесс. Для Ã все три совокупности совпадают, а для А. вычитания столбиком – нет: возможными исходными данными служат пары чисел, возможными результатами – числа (все в десятичной системе), а промежуточные результаты суть «трёхэтажные» записи вида
где q — есть запись числа в десятичной системе, r – такая запись или пустое слово, а р – запись числа в десятичной системе с допущением точек над некоторыми цифрами.
Работа А. начинается подготовительным шагом, на котором возможное исходное данное преобразуется в начальный член ряда сменяющих друг друга промежуточных результатов; это преобразование происходит на основе специального, входящего в состав рассматриваемого А. «правила начала». Это правило для Ã состоит в применении тождественного преобразования, а для А. вычитания – в замене пары<а, b> на запись
Затем применяется «правило непосредственной переработки», осуществляющее последовательные преобразования каждого возникающего промежуточного результата в следующий. Эти преобразования происходят до тех пор, пока некоторое испытание, которому подвергаются все промежуточные результаты по мере их возникновения, не покажет, что данный промежуточный результат является заключительным; это испытание производится на основе специального «правила окончания». Например, для Ã правило окончания состоит в проверке, не начинается ли промежуточный результат на aa. (Если ни для какого из возникающих промежуточных результатов правило окончания не даёт сигнала остановки, то либо к каждому из возникающих промежуточных результатов применимо правило непосредственной переработки, и алгоритмический процесс продолжается неограниченно, либо же к некоторому промежуточному результату правило непосредственной переработки оказывается неприменимым, и процесс оканчивается безрезультатно.) Наконец, из заключительного промежуточного результата – также на основе специального правила – извлекается окончательный результат; для Ã это извлечение состоит в отбрасывании первых двух букв а, а для А. вычитания – в отбрасывании всего, кроме самой нижней строчки цифр. (Во многих важных случаях правило начала и правило извлечения результата задают тождественные преобразования и потому отдельно не формулируются.) Т. о., для каждого А. можно выделить 7 характеризующих его (не независимых!) параметров: 1) совокупность возможных исходных данных, 2) совокупность возможных результатов, 3) совокупность промежуточных результатов, 4) правило начала, 5) правило непосредственной переработки, 6) правило окончания, 7) правило извлечения результата.
«Уточнения» понятия А. Возможны дальнейшие «уточнения» понятия А., приводящие, строго говоря, к известному сужению этого понятия. Каждое такое уточнение состоит в том, что для каждого из указанных 7 параметров А. точно описывается некоторый класс, в пределах которого этот параметр может меняться. Выбор этих классов и отличает одно уточнение от другого. Во многих уточнениях все классы, кроме двух – класса совокупностей промежуточных результатов и класса правил непосредственной переработки, – выбираются единичными, т. е. все параметры, кроме указанных двух, жестко фиксируются. Поскольку 7 параметров однозначно определяют некоторый А., то выбор 7 классов изменения этих параметров определяет некоторый класс А. Однако такой выбор может претендовать на название «уточнения», лишь если имеется убеждение, что для произвольного А., имеющего допускаемые данным выбором совокупности возможных исходных данных и возможных результатов, может быть указан равносильный ему А. из определённого данным выбором класса А. Это убеждение формулируется для каждого уточнения в виде основной гипотезы, которая – при современном уровне наших представлений – не может быть предметом математического доказательства.
Первые уточнения описанного типа предложили в 1936 американский математик Э. Л. Пост и английский математик А. М. Тьюринг (см. Тьюринга машина ). Известны также уточнения, сформулированные советскими математиками А. А. Марковым (см. Нормальный алгоритм ) и А. Н. Колмогоровым (последний предложил трактовать конструктивные объекты как топологические комплексы определённого вида, что дало возможность уточнить свойство «локальности» преобразования). Для каждого из предложенных уточнений соответствующая основная гипотеза хорошо согласуется с практикой. В пользу этой гипотезы говорит и то, что, как можно доказать, все предложенные уточнения в некотором естественном смысле эквивалентны друг другу.
В качестве примера приведём (в модернизированном виде) уточнение, предложенное Тьюрингом. Чтобы задать тьюрингов А., надо указать: а) попарно непересекающиеся алфавиты Б, Д, Ч с выделенной в Д буквой l и выделенными в Ч буквами a и w, б) набор пар вида < рx, hTq >, где р, qÎЧ, x, hÎБÈД, а Т есть один из знаков —, 0, +, причём предполагается, что в этом наборе (называемой программой) нет 2 пар с одинаковыми первыми членами. Параметры А. задаются так: возможными исходными данными и возможными результатами служат слова в Б, а промежуточными результатами – слова в БÈДÈЧ, содержащие не более одной буквы из Ч. Правило начала: исходное слово Р переводится в слово laРl. Правило окончания: заключительным является промежуточный результат, содержащий w. Правило извлечения результата: результатом объявляется цепочка всех тех букв заключительного промежуточного результата, которая идёт вслед за w. и предшествует первой букве, не принадлежащей Б. Правило непосредственной переработки, переводящее А в А', состоит в следующем. Приписываем к А слева и справа букву l; затем в образовавшемся слове часть вида erx, где рÎЧ, заменяем на слово Q по следующему правилу: в программе ищется пара с первым членом рx; пусть второй член этой пары есть hTq; если Т есть - , то Q = qeh, ЕСли Т есть 0, то Q =eqh; если Т есть +, то О = ehq. Возникающее после этой замены слово и есть А'.
