Другие подходы к определению понятия алгоритма. Тезис Черча

а) Гедель-Эбран-Клини: общерекурсивные функции, определенные с помощью исчисления «рекурсивных уравнений». Книга: Мендельсон. Введение в матем. Логику.- М.: Наука, 1976.-320 с.

б) Пост: Функции, определенные каноническими дедуктивными системами. Книга: Катленд Н. Вычислимость. Введение в теорию рекурсивных функций.-М.: Мир, 1983.-256 с.

в) Марков: Функции, задаваемыми «нормальными алгоритмами» над конечным алфавитом. Книга: Мендельсон. Введение в матем. Логику.- М.: Наука, 1976.-320 с.

г) Шепердсон-Стерджис: МНР-вычислимые функции (Катленд……..)

ТЕЗИС ЧЕРЧА: Интуитивно и неформально определенный класс эффективно вычислимых функций совпадает с классом определимых функций.

Вера в тезис подкрепляется аргументами:

1) многие независимые варианты уточнения интуитивного понятия вычислимости привели к одному и тому же классу;

2) обширное семейство эффективно вычислимых функций принадлежат этому классу;

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