Примеры статей
Алгоритм
Алгоритм, алгорифм, одно из основных понятий (категорий) математики, не обладающих формальным определением в терминах более простых понятий, а абстрагируемых непосредственно из опыта. А. являются…
Математический интуиционизм
Математический интуиционизм, философско-математическое течение, отвергающее теоретико-множественную трактовку математики и считающее интуицию единственным источником математики и главным критерием…
Брауэр Лёйтзен Эгберт Ян
Брауэр (Brouwer) Лёйтзен Эгберт Ян (27.2.1881, Оверсхи,-2.12.1966, Амстердам), голландский математик, член Нидерландской АН в Амстердаме (1912), член-корреспондент Парижской и Гёттингенской АН…
Вейль Герман
Вейль (Weyl) Герман (9.11.1885, Эльмсхорн, Шлезвиг-Гольштейн, - 8.12.1955, Цюрих), немецкий математик. Окончил Гёттингенский университет (1908). В 1913-30 профессор Цюрихского политехнического…
Чёрч Алонзо
Чёрч (Church) Алонзо (р 14.6.1903, Вашингтон), американский логик, математик. Профессор Принстонского университета (1947-1967). С 1967 профессор математики и философии Калифорнийского университета (…
Вычислимая функция
Вычислимая функция, одно из основных понятий теории алгоритмов. Функция f называется вычислимой, если существует алгоритм, перерабатывающий всякий объект х, для которого определена функция f, в объект…
Тьюринг Алан Матисон
Тьюринг (Turing) Алан Матисон (23.6.1912, Лондон, - 7.6.1954, Уилмслоу, близ Манчестера), английский математик. Член Королевского общества (1951). По окончании Кембриджского университета (1935)…
Пост Эмиль Леон
Пост (Post) Эмиль Леон (11.2.1897, Августов, Польша, - 21.4,1954, Нью-Йорк), американский математик и логик. Читал лекции по математике и логике в Колумбийском, Нью-Иоркском и др. университетах США…
Тьюринга машина
Тьюринга машина, название, закрепившееся за абстрактными (воображаемыми) "вычислительными машинами" некоторого точно охарактеризованного типа, дающими пригодное для целей математического рассмотрения…
Клини Стивен Коул
Клини (Kleene) Стивен Коул (р.5.1.1909, Хартфорд, штат Коннектикут), американский логик и математик. В 1934 получил степень доктора философии в Принстонском университете. Профессор Висконсинского…
Марков Андрей Андреевич (советский математик)
Марков Андрей Андреевич [родился 9(22).9.1903, Петербург], советский математик член-корреспондент АН СССР (1953). Член КПСС с 1953. Сын русского математика А. А. Маркова. Окончил Ленинградский…
Нормальный алгорифм
Нормальный алгорифм, одно из современных уточнений понятия алгоритма, получившее распространение в исследованиях по конструктивной математике. Предложено в 1950 А. А. Марковым, впервые систематически…
Колмогоров Андрей Николаевич
Колмогоров Андрей Николаевич [р.12(25).4.1903, Тамбов], советский математик, академик АН СССР (1939), Герой Социалистического Труда (1963). Окончил Московский университет (1925), с 1931 профессор там…
Разрешимое множество
Разрешимое множество в логике, множество, расположенное в некоторой совокупности конструктивных объектов (т. е. множество, составленное из каких-то объектов этой совокупности), для которого существует…
Перечислимое
Перечислимоемножество, рекурсивно-перечислимое множество, множество натуральных чисел или каких-либо других конструктивных объектов, занумерованных натуральными числами, являющееся множеством значений…
Алгоритм
Алгоритм, алгорифм, одно из основных понятий (категорий) математики, не обладающих формальным определением в терминах более простых понятий, а абстрагируемых непосредственно из опыта. А. являются…
Тарский Альфред
Тарский (Tarski) Альфред (р. 14.1. 1902, Варшава), польский логик и математик (с 1939 живёт в США). Полученные Т. результаты относятся к теории множеств, теории булевых алгебр, логикам с формулами…
Мальцев Анатолий Иванович
Мальцев Анатолий Иванович [14(27). 11.1909, ныне посёлок Мишеронский Шатурского района Московской области, - 7.7.1967, Новосибирск], советский математик, академик АН СССР (1958; член-корреспондент…
Новиков Петр Сергеевич
Новиков Петр Сергеевич [р. 15(28).8. 1901, Москва], советский математик, академик АН СССР (1960; член-корреспондент 1953). Окончил Московский университет (1925). В 1929-34 работал в Московском…
Исчисление
Исчисление, основанный на чётко сформулированных правилах формальный аппарат оперирования со знаками определённого вида, позволяющий дать исчерпывающе точное описание некоторого класса задач, а для…
Гёдель Курт
Гёдель (Godel) Курт [р. 28.4.1906, Брюнн (Брно)], австрийский логик и математик. В 1933-38 приват-доцент Венского университета. В 1940 эмигрировал в США; с 1953 профессор института перспективных…
Конструктивное направление
Конструктивное направление в математике, математическое мировоззрение, связанное с признанием исследования конструктивных процессов и конструктивных объектов основной задачей математики. К концу 19 в…
Информации теория
Информации теория, математическая дисциплина, исследующая процессы хранения, преобразования и передачи информации. И. т. - существенная часть кибернетики. В основе И. т. лежит определённый способ…
Алгоритмов теория
Алгоритмов теория, раздел математики, изучающий общие свойства алгоритмов. Содержательные явления, приведшие к образованию понятия "алгоритм", прослеживаются в математике в течение всего времени её существования. Однако само это понятие сформировалось лишь в 20 в. и стало предметом самостоятельного изучения (по-видимому, впервые, хотя ещё в расплывчатом виде) лишь в 20-х гг. 20 в. в трудах представителей математического интуиционизма Л. Э. Я. Брауэра и Г. Вейля. Началом систематической разработки А. т. можно считать 1936, когда А. Чёрч опубликовал первое уточнение понятия вычислимой функции (предложив отождествлять понятие всюду определённой вычислимой функции, имеющей натуральные аргументы и значения, с понятием общерекурсивной функции) и привёл первый пример функции, не являющейся вычислимой, а А. М. Тьюринг и Э. Л. Пост дали первые уточнения понятия алгоритма (в терминах идеализированных вычислительных машин, см. Тьюринга машина). В дальнейшем А. т. получила развитие в трудах С. К. Клини, Э. Л. Поста, А. А. Маркова и других. В частности, А. А. Марков предложил уточнять понятие алгоритма с помощью введённого им понятия нормального алгоритма. Наиболее общий подход к уточнению понятия алгоритма предложил А. Н. Колмогоров.
Основные понятия А. т. Областью применимости алгоритма называется совокупность тех объектов, к которым он применим. Про алгоритм Á говорят, что он: 1) "вычисляет функцию f", коль скоро его область применимости совпадает с областью определения f и Á перерабатывает всякий x из своей области применимости в f(x), 2) "разрешает множество А относительно множества X", коль скоро он применим ко всякому х из Х и перерабатывает всякий х из Х Ç A в слово "да", а всякий х из Х\A в слово "нет"; 3) "перечисляет множество В", коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть В. Функция называется вычислимой, если существует вычисляющий её алгоритм. Множество называется разрешимым относительно X, если существует разрешающий его относительно Х алгоритм (см. Разрешимое множество). Множество называется перечислимым, если либо оно пусто, либо существует перечисляющий его алгоритм (см. Перечислимое множество).
Детальный анализ понятия "алгоритм" обнаруживает, что (I) область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества. В свою очередь (II) для любой пары вложенных одно в другое перечислимых множеств можно подобрать алгоритм, у которого большее множество служит множеством исходных данных, а меньшее — областью применимости. Имеют место следующие основные теоремы: (III) функция f вычислима тогда и только тогда, когда перечислим её график, т. е. множество всех пар вида <x, f(x)>. (IV) Подмножество А перечислимого множества Х тогда и только тогда разрешимо относительно X, когда А и Х \А перечислимы. (V) Если А и В перечислимы, то A' ÈB и А ÇВ также перечислимы. (VI) В каждом бесконечном перечислимом множестве Х существует перечислимое подмножество с неперечислимым дополнением [в силу (IV) это перечислимое подмножество будет неразрешимым относительно X]. (VII) Для каждого бесконечного перечислимого множества Х существует вычислимая функция, определённая на подмножестве этого множества и не продолжаемая до вычислимой функции, определённой на всём X. Утверждения (VI) и (II) в совокупности дают упоминаемый в ст. Алгоритм пример алгоритма Á с неразрешимой областью применимости.
Алгоритмические проблемы. Проблема построения алгоритма, обладающего теми или иными свойствами, называется алгоритмической проблемой (а. п.). Как правило, свойство искомого алгоритма формулируется в терминах свойств того соответствия, которое должно иметь место между исходными данными и результатами алгоритма. Важные примеры а. п.: проблема вычисления данной функции (требуется построить алгоритм, вычисляющий эту функцию): проблема разрешения данного множества (требуется построить алгоритм, разрешающий это множество относительно некоторого другого множества); проблема перечисления данного множества (требуется построить алгоритм, перечисляющий данное множество). Неразрешимость а. п. означает отсутствие соответствующего алгоритма; теоремы, устанавливающие неразрешимость таких проблем, относятся к числу наиболее важных теорем А. т.
Метрическая А. т. А. т. можно разделить на дескриптивную (качественную) и метрическую (количественную). Первая исследует алгоритмы с точки зрения устанавливаемого ими соответствия между исходными данными и результатами, к ней относятся, в частности, те алгоритмические проблемы, о которых говорилось в предыдущем разделе. Вторая исследует алгоритмы с точки зрения сложности как самих алгоритмов, так и задаваемых ими "вычислений", т. е. процессов последовательного преобразования конструктивных объектов. Важно подчеркнуть, что сложность алгоритмов и вычислений может определяться различными способами, причём может оказаться, что при одном способе А будет сложнее В, а при другом способе — наоборот. Чтобы говорить о сложности алгоритмов, надо сперва описать какой-либо точный язык для записи алгоритмов и затем под сложностью алгоритма понимать сложность его записи; сложность же записи можно определять различными способами (например, как число символов данного типа, участвующих в записи, или как набор таких чисел, вычисленных для разных типов символов). Чтобы говорить о сложности вычисления, надо уточнить, как именно вычисление представляется в виде цепочки сменяющих друг друга конструктивных объектов и что считается сложностью такой цепочки (только ли число членов в ней — "число шагов" вычисления или ещё учитывается "размер" этих членов и т. п.); в любом случае сложность вычисления зависит от исходного данного, с которого начинается вычисление, поэтому сложность вычисления есть функция, сопоставляющая с каждым объектом из области применимости алгоритма сложность соответствующей цепочки. Разработка методов оценки сложности алгоритмов и вычислений имеет важное теоретическое и практическое значение, однако в отличие от дескриптивной А. т., оформившейся в целостную математическую дисциплину, метрическая А. т. делает лишь первые шаги.
Приложения А. т. имеются во всех областях математики, в которых встречаются алгоритмические проблемы. Такие проблемы возникают в математической логике и теории моделей; для каждой теории формулируется проблема разрешения множества всех истинных или доказуемых предложений этой теории относительно множества всех её предложений (теории подразделяются на разрешимые и неразрешимые — в зависимости от разрешимости или неразрешимости указанной проблемы); в 1936 А. Чёрч установил неразрешимость проблемы разрешения для множества всех истинных предложений логики предикатов, дальнейшие важные результаты в этом направлении принадлежат А. Тарскому, А. И. Мальцеву и др. Алгоритмические проблемы встречаются в алгебре (проблема тождества для полугрупп и, в частности, для групп: первые примеры полугрупп с неразрешимой проблемой тождества были найдены в 1947 независимо А. А. Марковым и Э. Л. Постом, а пример группы с неразрешимой проблемой тождества — в 1952 П. С. Новиковым); в топологии (проблема гомеоморфии, неразрешимость которой для важного класса случаев была доказана в 1958 А. А. Марковым); в теории чисел (остающаяся до сих пор открытой проблема разрешимости диофантовых уравнений) и др. разделах математики.
А. т. тесно связана с математической логикой, поскольку на понятие алгоритма опирается одно из центральных понятий математической логики — понятие исчисления и потому, например, теорема К. Гёделя о неполноте формальных систем может быть получена как следствие теорем А. т. Наконец, А. т. тесно связана с основаниями математики, в которых одно из центральных мест занимает проблема соотношения конструктивного и неконструктивного, в частности А. т. даёт аппарат, необходимый для разработки конструктивного направления в математике; в 1965 А. Н. Колмогоров предложил использовать А. т. для обоснования информации теории. А. т. образует теоретический фундамент для ряда вопросов вычислительной математики и тесно связана с кибернетикой, в которой важное место занимает изучение алгоритмов управления, в частности понятие алгоритма занимает центральное место в т. н. программированном обучении.
Лит.: Общие вопросы. Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; Марков А. А., Теория алгорифмов, М. — Л., 1954 (Тр. Матем. института АН СССР, т. 42).
Отдельные вопросы. Колмогоров А. Н., Три подхода к определению понятия "количество информации", "Проблемы передачи информации", 1965, т. 1, в. 1; Ершов Ю. Л. [и др.], Элементарные теории, "Успехи математических наук", 1965, т. 20, в. 4; Марков А. А., О нормальных алгорифмах, связанных с вычислением булевых функций, "Известия АН СССР. Серия математическая", 1967, т. 31, в. 1; Трахтенброт Б. А., Сложность алгоритмов и вычислений, Новосиб., 1967.
В. А. Успенский.