Тезис Чёрча-Тьюринга

Интуитивно и неформально определённый класс эффективно вычислимых частичных функций совпадает с классом лямбда-определимых (равно как вычислимых по Тьюрингу и т.д.) функций.

Свидетельства в пользу тезиса

1. Фундаментальный результат: независимые варианты интуитивного понятия вычислимости сводятся один к другому.
2. Показано, что обширное семейство функций принадлежит к классу вычислимых в той или иной модели (т.е. может быть "запрограммировано").
3. Какую бы программу в конкретной модели мы не взяли, реализуемая ею функция, очевидно, является эффективно вычислимой.
4. Никому не доводилось найти функцию, вычислимую в неформальном смысле, не принадлежащую ни одному из классов.

Следствия

1. Когда требуется доказать, что функция принадлежит некоторому классу, можно
   • либо пытаться её запрограммировать непосредственно на соответствующем формализме,
   • либо неформально показать, что она описывается алгоритмом; тогда в силу тезиса её можно считать вычислимой.
2. Все формальные модели могут одинаково успешно применяться для исследования свойств механических вычислителей.