Алгоритмів теорія, розділ математики, що вивчає загальні властивості алгоритмів . Змістовні явища, що привели до утворення поняття «алгоритм», просліджуються в математиці протягом всього часу її існування. Проте само це поняття сформувалося лише в 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) У кожній безконечній безлічі Х , що перераховує, існує підмножина, що перераховує, з доповненням, що не перераховує [в силу це підмножина, що перераховує, буде нерозв'язною відносне X]. (VII) Для кожної безконечної безлічі, що перераховує, Х існує обчислювана функція, що визначена на підмножині цієї безлічі і не продовжується до обчислюваної функції, визначеної на всьому X. Твердження (VI) і (II) в сукупності дають згадуваний в ст. Алгоритм приклад алгоритму Á з нерозв'язною областю застосовності.
Алгоритмічні проблеми. Проблема побудови алгоритму, що володіє тими або іншими властивостями, називається алгоритмічною проблемою (а. п.). Як правило, властивість шуканого алгоритму формулюється в термінах властивостей тієї відповідності, яка повинна мати місце між вихідними даними і результатами алгоритму. Важливі приклади а. п.: проблема обчислення даної функції (потрібно побудувати алгоритм, що обчислює цю функцію): проблема дозволу даної безлічі (потрібно побудувати алгоритм, що вирішує цю безліч відносно деякого іншого безліч); проблема перерахування даної безлічі (потрібно побудувати алгоритм, що перераховує дану безліч). Нерозв'зність а. п. означає відсутність відповідного алгоритму; теореми, що встановлюють нерозв'зність таких проблем, належать до найбільш важливих теорем А. т.
Метрична А. т. А. т. можна розділити на дескриптивну (якісну) і метричну (кількісну). Перша досліджує алгоритми з точки зору встановлюваної ними відповідності між вихідними даними і результатами, до неї відносяться, зокрема, ті алгоритмічні проблеми, про які говорилося в попередньому розділі. Друга досліджує алгоритми з точки зору складності як самих алгоритмів, так і «обчислень», що задаються ними, тобто процесів послідовного перетворення конструктивних об'єктів. Поважно підкреслити, що складність алгоритмів і обчислень може визначатися різними способами, причому може виявитися, що при одному способі А буде складніше В, а при іншому способі — навпаки. Щоб говорити про складність алгоритмів, треба спершу описати яку-небудь точну мову для запису алгоритмів і потім під складністю алгоритму розуміти складність його запису; складність же запису можна визначати різними способами (наприклад, як число символів даного типа, що беруть участь в записі, або як набір таких чисел, обчислених для різних типів символів). Щоб говорити про складність обчислення, треба уточнити, як саме обчислення представляється у вигляді ланцюжка конструктивних об'єктів, що змінюють один одного, і що вважається складністю такого ланцюжка (чи лише число членів в ній — «число кроків» обчислення або ще враховується «розмір» цих членів і т. п.); у будь-якому випадку складність обчислення залежить від вихідного даного, з якого починається обчислення, тому складність обчислення є функція, що зіставляє з кожним об'єктом з області застосовності алгоритму складність відповідного ланцюжка. Розробка методів оцінки складності алгоритмів і обчислень має важливе теоретичне і практичне значення, проте на відміну від дескриптивної А. т., що оформилася в цілісну математичну дисципліну, метрична А. т. робить лише перші кроки.
Застосування А. т. є у всіх областях математики, в яких зустрічаються алгоритмічні проблеми. Такі проблеми виникають в математичній логіці і теорії моделей; для кожної теорії формулюється проблема дозволу безлічі всіх дійсних або доказових пропозицій цієї теорії відносно безлічі всіх її пропозицій (теорії підрозділяються на вирішуваних і нерозв'язних — залежно від вирішуваної або нерозв'зності вказаної проблеми); у 1936 А. Черч встановив нерозв'зність проблеми дозволу для безлічі всіх дійсних пропозицій логіки предикатів, подальші важливі результати в цьому напрямі належать А. Тарському, А. І. Мальцеву і ін. Алгоритмічні проблеми зустрічаються в алгебрі (проблема тотожності для напівгруп і, зокрема, для груп: перші приклади напівгруп з нерозв'язною проблемою тотожності були знайдені в 1947 незалежно А. А. Марковим і Е. Л. Постом, а приклад групи з нерозв'язною проблемою тотожності — в 1952 П. С. Новіковим ) ; в топології (проблема гомеоморфії, нерозв'зність якої для важливого класу випадків була доведена в 1958 А. А. Марковом); у теорії чисел (що залишається до цих пір відкритою проблема вирішуваної діофантових рівнянь) і ін. розділах математики.
А. т. тісно пов'язана з математичною логікою, оскільки на поняття алгоритму спирається одне з центральних понять математичної логіки — поняття числення і тому, наприклад, теорема До. Геделя про неповноту формальних систем може бути отримана як наслідок теорем А. т. Нарешті, А. т. тісно пов'язана з підставами математики, в яких одне з центральних місць займає проблема співвідношення конструктивного і неконструктивного, зокрема А. т. дає апарат, необхідний для розробки конструктивного напряму в математиці; у 1965 А. Н. Колмогоров запропонував використовувати А. т. для обгрунтування інформації теорії . А. т. утворює теоретичний фундамент для низки запитань обчислювальної математики і тісно пов'язана з кібернетикою, в якій важливе місце займає вивчення алгоритмів управління, зокрема поняття алгоритму займає центральне місце В т. н. програмованому вченні.
Літ.: Загальні питання. Мальцев А. І., Алгоритми і рекурсивні функції, М., 1965; Марков А. А., Теорія алгоріфмов, М. — Л., 1954 (Тр. Матем. інституту АН(Академія наук) СРСР, т. 42).
Окремі питання . Колмогоров А. Н., Три підходи до визначення поняття «Кількість інформації», «Проблеми передачі інформації», 1965, т. 1, ст 1; Ершов Ю. Л. [і ін.], Елементарні теорії, «Успіхи математичних наук», 1965, т. 20, ст 4; Марков А. А., Про нормальні алгоріфмах, пов'язаних з обчисленням булевих функцій, «Вісті АН(Академія наук) СРСР. Серія математична», 1967, т. 31, ст 1; Трахтенброт Би. А., Складність алгоритмів і обчислень Новосиб., 1967.
