2. Подходы к формализации понятий алгоритмов и вычислимых функций в теории алгоритмов.

Известно несколько подходов к формализации понятия «алгоритм»:

* теория конечных и бесконечных автоматов;

* теория вычислимых (рекурсивных) функций;

* л-исчисление Черча.

Все эти возникшие исторически независимо друг от друга подходы оказались впоследствии эквивалентными. Главная цель формализации понятия алгоритма такова: подойти к решению проблемы алгоритмической разрешимости различных математических задач, т.е. ответить на вопрос, может ли быть построен алгоритм, приводящий к решению задачи. 

Функция f с натуральными аргументами и значениями называется вычислимой, если существует алгоритм, ее вычисляющий, то есть такой алгоритм A, что

• если f(n) определено для некоторого натурального n, то алгоритм A останавливается на входе n и печатает f(n) ;

• если f(n) не определено, то алгоритм A не останавливается на входе n.

Несколько замечаний по поводу этого определения:

Понятие вычислимости определяется здесь для частичных функций (областью определения которых является некоторое подмножество натурального ряда). Например, нигде не определенная функция вычислима (в качестве A надо взять программу, которая всегда зацикливается).

Можно было бы изменить определение, сказав так: " если f(n) не определено, то либо алгоритм A не останавливается, либо останавливается, но ничего не печатает ". На самом деле от этого ничего бы не изменилось (вместо того, чтобы останавливаться, ничего не напечатав, алгоритм может зацикливаться).

Входами и выходами алгоритмов могут быть не только натуральные числа, но и двоичные строки (слова в алфавите {0,1} ), пары натуральных чисел, конечные последовательности слов и вообще любые, как говорят, " конструктивные объекты ". Поэтому аналогичным образом можно определить понятие, скажем, вычислимой функции с двумя натуральными аргументами, значениями которой являются рациональные числа. Для функций, скажем, с действительными аргументами и значениями понятие вычислимости требует специального определения. Здесь ситуация сложнее, определения могут быть разными, и мы о вычислимости таких функций говорить не будем. Отметим только, что, например, синус (при разумном определении вычислимости) вычислим, а функция sign(x), равная -1, 0 и 1 при x < 0, x = 0 и x > 0 соответственно - нет. Точно так же требует специального определения вычислимость функций, аргументами которых являются бесконечные последовательности нулей и единиц и т.п.

Несколько десятилетий назад понятие алгоритма требовало специального разъяснения. Сейчас (" компьютерная грамотность "?) такие объяснения все равно никто читать не будет, поскольку и так ясно, что такое алгоритм. Но все же надо соблюдать осторожность, чтобы не принять за алгоритм то, что им не является. Вот пример неверного рассуждения:

" Докажем", что всякая вычислимая функция f с натуральными аргументами и значениями может быть продолжена до всюду определенной вычислимой функции g: N -> N . В самом деле, если f вычисляется алгоритмом A, то следующий алгоритм B вычисляет функцию g, продолжающую f: " если A останавливается на n, то B дает тот же результат, что и A ; если A не останавливается на n, то B дает результат (скажем) 0 ".