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

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендуемая литература: /2, 3, 6, 7, 8, 9, 12, 14, 19 /.