АЛГОРИТМЫ И РЕКУРСИВНЫЕ ФУНКЦИИ

Каждый алгоритм имеет входные и выходные данные и состоит из конечного числа инструкций. Например, алгоритм Евклида имеет на входе два положительных числа a и b, на выходе – их наибольший общий делитель. В качестве инструкций можно рассмотреть следующие команды:

1) сравнить a и b;

2) если a равно b, то установить наибольший общий делитель, равным a, и закончить работу;

3) если a > b, то установить a = a – b и перейти к 1;

если b > a, то установить b = b – a и перейти к 1.

Развитие математики требовало уточнения понятия алгоритма в связи с вопросами алгоритмической разрешимости проблем. Следующие свойства алгоритма были признаны характеризующими его среди методов построения математических объектов:

а) алгоритм состоит из шагов, на каждом из которых формируется система объектов, построенных в предшествующие моменты (дискретность алгоритма);

б) эта система объектов однозначно определяется системой в предшествующие моменты (детерминированность);

в) закон получения последующей системы объектов из предшествующих должен быть простым (элементарность шагов);

г) способ получения объектов на каждом шаге должен давать результаты (направленность);

д) начальная система объектов может выбираться из бесконечного множества (массовость).

Мы рассмотрим алгоритмы, используемые для вычисления значений числовых функций. Такие функции называются вычислимыми.

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

Частично рекурсивные функции

Под числовыми функциями мы понимаем функции f: Nⁿ ® N, где N = w – множество всех натуральных чисел x ³ 0, Nⁿ = {(x₁,…,x_n): x₁ÎN,…,x_nÎN} – его декартова степень. Эти функции называются n-местными. Функцией N⁰ ® N, зависящей от 0 переменных, называется произвольная константа cÎN. Частичной (числовой) n-местной функцией называется функция f: D ® N, определенная на некотором подмножестве D Í Nⁿ декартовой степени. Обозначим D через Dom(f) и будем называть её областью определения частичной функции f. Для частичной n-местной функции f будем применять обозначения f: Nⁿ ® N.

Простейшие функции

Функции s: N ® N, 0: N⁰ ® N и Iⁿ_m: Nⁿ ® N, принимающие значения s(x) = x + 1, константа 0 и Iⁿ_m(x₁,…,x_n) = x_m, для всех x, x₁,…,x_n Î N и n ³ m ³ 1, называются простейшими. Операции над функциями будут называться операторами.