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

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

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