Тезис Чёрча — Тьюринга
Гипотеза: всё, что интуитивно «эффективно вычислимо», вычислимо на машине Тьюринга (или в лямбда-исчислении, ей эквивалентном). Это не доказуемая теорема, а определение «вычислимого».
Чёрч и Тьюринг пришли к нему независимо в 1936 году. Следствие: все «разумные» модели вычислений (машины Тьюринга, лямбда-исчисление, регистровые машины, рекурсивные функции, клеточные автоматы, «Жизнь» Конвея) эквивалентны. Современное расширение — сильный тезис Чёрча — Тьюринга: все эффективно вычислимые функции полиномиально эквивалентны. Квантовые вычисления ставят под вопрос сильную версию (алгоритм Шора факторизует за полиномиальное время, классические методы — нет).