Характерной чертой современности является широкое использование компьютеров при решении проблем (задач) в различных областях человеческой деятельности. Однако предварительно задача должна быть решена алгоритмически, т.е. должно быть задано формальное предписание, следуя которому можно получить итоговый результат для решения всех задач определенного типа (это интуитивное, не строгое понятие алгоритма). Например, алгоритм нахождения наибольшего общего делителя двух натуральных чисел а, b, выглядит следующим образом:

1) разложить число a на простые множители;

2) повторить п. 1 для b и перейти к п. 3;

3) составить произведение общих простых множителей из разложений а и b с показателями, равными наименьшим из показателей вхождения в разложения.

Проанализировав этот пример, отметим важнейшие черты (свойства) алгоритма:

1. Массовость — применимость алгоритма не к одной задаче, а к классу задач.

2. Дискретность — четкая разбивка на отдельные этапы (шаги) алгоритма.

3. Детерминированность — такая организация этапов выполнения, при которой всегда ясно как осуществить переход от одного этапа к другому.

4. Конечность — для получения результата при применении алгоритма к решению конкретной задачи выполняется конечная последовательность шагов алгоритма.

Отметим, что если наличие алгоритма само по себе служит доказательством существования алгоритма, то для доказательства его отсутствия необходимо иметь строгое математическое определение алгоритма.

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

Тезис Чёрча. Понятие алгоритма, или вычислимости некоторым механическим устройством, совпадает с понятием вычислимости на машинах Тьюринга (а значит, с понятием рекурсивной функции). Другими словами, алгоритм — это процесс, который может быть представлен функциональной схемой и реализован некоторой машиной Тьюринга.

Это утверждение нельзя считать математической теоремой. Это есть некоторый естественнонаучный тезис, принятый большинством исследователей.