Приложения А.
т. имеются во всех областях математики, в которых встречаются алгорнтмич.
проблемы. Такие проблемы возникают в матем. логике и теории моделей; для
каждой теории формулируется проблема разрешения множества всех истинных
или доказуемых предложений этой теории относительно множества всех её предложений
(теории подразделяются на разрешимые и неразрешимые - в зависимости от
разрешимости или неразрешимости указанной проблемы); в 1936 А. Чёрч установил
неразрешимость проблемы разрешения для множества всех истинных предложений
логики предикатов, дальнейшие важные результаты в этом направлении принадлежат
А. Тарскому, А. И. Мальцеву и др. Алгоритмич. проблемы встречаются в алгебре
(проблема тождества для полугрупп и, в частности, для групп; первые примеры
полугрупп с неразрешимой проблемой тождества были найдены в 1947 независимо
А. А. Марковым и Э. Л. Постом, а пример группы с неразрешимой проблемой
тождества- в 1952 П. С. Новиковым); в топологии (проблема гомеоморфии,
неразрешимость к-рой для важного класса случаев была доказана в 1958 А.
А. Марковым); в теории чисел (остающаяся до сих пор открытой проблема разрешимости
диофантовых уравнений) и др. разделах математики.
А. т. тесно
связана с матем. логикой, поскольку на понятие алгоритма опирается одно
из центральных понятий матем. логики - понятие исчисления и потому, напр.,
теорема К. Гёделя о неполноте формальных систем может быть получена как
следствие теорем А. т. Наконец, А. т. тесно связана с основаниями математики,
в к-рых одно из центральных мест занимает проблема соотношения конструктивного
и неконструктивного, в частности А. т. даёт аппарат, необходимый для разработки
конструктивного направления в математикев; 1965 А. Н. Колмогоров предложил
использовать А. т. для обоснования информации теории. А. т. образует теоретич.
фундамент для ряда вопросов вычислит, математики и тесно связана с кибернетикой,
в к-рой важное место занимает изучение алгоритмов управления, в частности
понятие алгоритма занимает центральное место в т. н. программированном
обучении.
Лит.: Общие
вопросы. Мальцев . А. И., Алгоритмы и рекурсивные функции, М., 1965; Марков
А. А., Теория алгорифмов, М.- Л., 1954 (Тр. Матем. института АН СССР, т.
42).
А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я