В 1935 г. возникло такое положение: свойства, обнаруженные у некоторого точно определенного класса вычислимых теоретико-числовых функций, изучавшихся Чёрчем и Клини в 1932—1935 гг. и названных «-определимыми функциями», упорно подсказывали мысль, что этот класс, может быть, охватывает все функции, которые в соответствии с нашим интуитивным представлением можно рассматривать как вычислимые. При этих обстоятельствах Чёрч выдвинул тезис (опубликован в 1936 г.), что все функции, которые интуитивно мы можем рассматривать как вычислимые, или, говоря его словами, как «эффективно вычислимые», являются -определимыми, или, эквивалентным образом, общерекурсивными.
Несколько позже, но независимо появилась статья Тьюринга (1936), в которой был введен еще один точно определенный класс интуитивно вычислимых функций, которые мы будем называть «функциями, вычислимыми по Тьюрингу», и относительно этого класса было высказано такое же утверждение; это утверждение мы называем тезисом Тьюринга. Вскоре Тьюрингом было показано, что его вычислимые функции — это то же самое, что -определимые функции, и, следовательно, то же самое, что и общерекурсивные функции. Поэтому тезисы Тьюринга и Чёрча эквивалентны. Мы будем обычно ссылаться на оба эти тезиса как на тезис Чёрча, а в связи с тем его вариантом, в котором идет речь о «машинах Тьюринга»,— как на тезис Чёрча — Тьюринга. В 1936 г. Пост независимо от Тьюринга опубликовал в довольно сжатом изложении формулировку, в основе ту же, что у Тьюринга. В 1943 г., основываясь на своей неопубликованной работе 1920— 1922 гг., он опубликовал третий эквивалент аналогичного тезиса. Еще одну эквивалентную формулировку дает теория алгоритмов Маркова .