Алгоритм (Кузнєцов)

АЛГОРИТМ (від algorismus — латинізоване ім’я середньоазіатського вченого IX ст. аль-Хорезмі) — чітко задана кінцева послідовність процедур, що приводить до вирішення будь-якої конкретної задачі з деякого класу завдань. Побудова А. для задач певного типу, тобто алгоритмізація їх вирішення, зводить пошук відповіді на поставлене ний питання до таких простих операцій, що вони можуть виконуватися чисто механічно, а тому можуть бути передані нікому пристрою (наприклад, комп’ютера), який і здійснить пошук відповіді згідно з приписом А.

Пошук А. для вирішення різного роду завдань завжди був важливою темою досліджень у математиці. Починаючи з середньовіччя добре відомі і увійшли в шкільний курс арифметики А. додавання, віднімання, множення і ділення «стовпчиком» в десятковій системі числення, А. знаходження найбільшого спільного дільника, А. знаходження коренів квадратних рівнянь і багато іншого. Розвиток сучасної логіки призвело до необхідності знаходження А. для вирішення багатьох задач цієї науки. Так, розпізнавання логічних законів у логіці висловлювань вирішується з допомогою А. побудови таблиць істинності. В даний час велика увага приділяється знаходженню зручних А. пошуку доведення теорем для різних логічних теорій.

Однак багато проблем математики і логіки протягом тривалого часу не піддавалися алгоритмізації. Виникли підозри, що для них взагалі не можна побудувати А. Для доказу такого роду негативною теорема (про існування А.) необхідно було початкове інтуїтивне поняття А. уточнити суворо формальним чином. Ця робота була виконана в 30 -50-х роках XX ст. і призвела до кількох еквівалентним один одному уточненням поняття А. Такими уточненнями є поняття абс-трактной машини Тюрінга, общерекурсивной функції, Л-определимой функції, нормального алгоритму Маркова і ряд інших. На основі цих уточнень були отримані результати про неіснування А. для багатьох завдань логіки і математики. Зокрема, А. Черчем була доведена теорема про існування А., який за будь-якою формулою первопорядковой логіки предикатів встановлював би, вона є законом цій логічній теорії чи ні.

У сучасній науці теорія А. є основою конструктивного напряму в математиці та логіці. Вона є базовою дисципліною в області обчислювальної техніки і програмування, машинного вирішення найрізноманітніших завдань, моделювання різних процесів.

Словник філософських термінів. Наукова редакція професора В. Р. Кузнєцова. М., ІНФРА-М, 2007, с. 7-8.