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

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

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

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

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

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

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

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

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

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

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

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

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

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