Советский философский словарь - алгоритм

Общая проблема совместно с требованием разыскания А. наз. алгоритмической. Если А. предложен, то спрашивается: всегда ли ответы по предложенному А. будут ответами на частные вопросы данной алгоритмич. проблемы? Это выясняют доказательством соответствия А. данной проблеме, после чего алгоритмич. проблему считают разрешимой А. (или алгоритмически разрешимой). Обычно задачи, решаемые А., сводятся к распознаванию свойств конструктивных объектов (см. Конструктивное направление). Напр., А. распознавания свойства общезначимости для формул логики высказываний даётся их табличной оценкой. Это же свойство характеризует и множество доказуемых формул исчисления высказываний, крос, т. о., алгоритмически разрешимо относительно истинности.

Вопрос о проблемах, разрешимых А., связан с вопросом об использовании машин вместо человека и пределах автоматизации процессов мышления. Вера в алгоритмич. разрешимость всех (по крайней мере, всех математич. и логич.) проблем имела значит, влияние в философии начиная с Декарта и Лейбница. В 1931 К. Гёдель доказал, что в системах аксиом определ. вида есть проблемы, неразрешимые А. этих систем, в связи с чем возник вопрос об описании класса всех возможных типов А. в рамках строгой (формальной) теории А. В 1936 появилось песк. вариантов стандартных систем уточнения понятия А. (формализации функций, вычислимых по Гёделю, Клини, Тьюрингу, Черчу) и была высказана эмпирически обоснованная гипотеза, что иных А., удовлетворяющих свойствам содержат. понятия А., но неэквивалентных стандартным формализациям, не существует. Эта гипотеза означала признание принципиальной завершённости поиска средств, привлекаемых для решения алгоритмич. проблем, и вместе с тем признание существова

ния алгоритмически «абсолютно неразрешимых» проблем. Однако подобные выводы отнюдь не ограничивали развитие салон теории А., ставшей с нач. 50-х гг. внутри логики и математики теоретич. основой конструктивизма, а в области вычислит, науки и техники основой машинного решения математич. задач, моделирования сложных процессов и автоматизации процессов произ-ва. Важный этап этого развития созданная А. А. Марковым теория нормальных А., уточняющая непосредственно интуитивное понятие А., и предложенная им формулировка осн. абстракций теории А.