Машина Тьюринга и рекурсивные функции. Кацаран Т.К - 5 стр.

     Массовость – алгоритм решения задачи разрабатывается в общем
виде, то есть, он должен быть применим для некоторого класса задач, раз-
личающихся только исходными данными. При этом исходные данные мо-
гут выбираться из некоторой области, которая называется областью при-
менимости алгоритма.
     Теория алгоритмов – это раздел математики, который изучает общие
свойства алгоритмов. Различают качественную и метрическую теорию ал-
горитмов.
     Основной проблемой качественной теории алгоритмов является про-
блема построения алгоритма, обладающего заданными свойствами. Такую
проблему называют алгоритмической.
     Метрическая теория алгоритмов исследует алгоритм с точки зрения
их сложности. Этот раздел теории алгоритмов известен также как алго-
ритмическая теория сложности.
     При отыскании решений некоторых задач долго не удавалось най-
ти соответствующий алгоритм. Примерами таких задач являются: а) ука-
зать способ, согласно которому для любой предикатной формулы за ко-
нечное число действий можно выяснить, является ли она тождественно-
истинной или нет; б) разрешимо ли в целых числах диофантово уравне-
ние (алгебраическое уравнение с целыми коэффициентами). Так как для
решения этих задач найти алгоритмов не удалось, возникло предполо-
жение, что такие алгоритмы вообще не существуют, что и доказано:
первая задача решена А. Черчем, а вторая – Ю.В. Матиясевичем и
Г.В. Чудновским. Доказать это с помощью интуитивного понятия алго-
ритма в принципе невозможно. Поэтому были предприняты попытки
дать точное математическое определение понятия алгоритма. В середине
30-х годов ХХ века С.К. Клини, А.А. Марков, Э. Пост, А. Тьюринг,
А. Черч и другие предположили различные математические определения

                                   5