Введение. Алгоритмы и рекурсивные функции

Раздел 7

Алгоритмы и рекурсивные функции.

Введение.

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

В наше время отмечают следующие характерные черты алгоритмов:

1) Дискретность алгоритма, т.е. вычисления согласно алгоритму производят по шагам, с четким предписанием: 1)…, 2)…, и т.д. (по программе).

2) Детерминированность алгоритма, т.е. величины, получаемые в процессе вычисления на любом последующем шаге, однозначно определяются величинами, полученными на предшествующем шаге.

3) Элементарность шагов алгоритма, т.е. правила, инструкции, по которым выполняется каждый шаг, должны быть четкими, понятными, не допускающие неопределенности.

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

5) Массовость алгоритма, т.е. возможность применения для решения бесконечного числа однотипных задач.

Отмеченные характерные черты алгоритма, конечно, не дают математически строгого определения алгоритма, т.к. точный смысл ряда терминов, встречающихся в них, не установлен.

И хотя понятие алгоритма в математике возникло очень давно, и у математиков не возникало споров относительно того, является ли какая-то описанная вычислительная процедура алгоритмом или нет, точного определения алгоритма не существовало до середины тридцатых годов ХХ века. Дело в том, что для построения конкретного алгоритма, точное определение алгоритма не обязательно, но для доказательства того, что для решения какой-то задачи не существует алгоритма, необходимо строгое определение его.

Рассматривая конкретные алгоритмы, можно сделать вывод, что мы находим способы вычисления некоторой целочисленной функции.

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

С другой стороны, вычисления согласно предписанию алгоритма можно рассматривать как механическую работу, которую можно поручить «машине». Работая в этом направлении, Пост и Тьюринг, независимо друг от друга, дали строгое определение «машины», способной выполнять конечное число простых операций. Работы Поста и Тьюринга появились одновременно с работами Черча и Клини. Оказалось, что класс функций, вычислимых на машинах Тьюринга, совпадает с классом частично-рекурсивных функций.