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

Тезис Чёрча — Тьюринга утверждает, что любая функция, вычислимая с помощью любой эффективной процедуры, вычислима машиной Тьюринга, приравнивая неформальное представление об алгоритме к точной математической модели.

Definition

Тезис Чёрча — Тьюринга — это утверждение о том, что интуитивно вычислимые функции — это в точности функции, вычислимые машиной Тьюринга, или, эквивалентно, лямбда-исчислением или общерекурсивными функциями; это тезис, а не теорема, поскольку интуитивное понятие не определено формально.

Scope

Эта тема охватывает формулировку тезиса, конвергентные доказательства из независимо предложенных моделей, различие между исходным тезисом об эффективной вычислимости и более сильными физическими или теоретико-сложностными вариантами, а также роль тезиса как моста между интуицией и формальным доказательством в теории вычислимости.

Core questions

• Что означает отождествление неформального понятия алгоритма с формальной моделью?
• Почему сходимость независимых моделей считается веским доказательством тезиса?
• Является ли тезис математической теоремой, определением или эмпирическим утверждением?
• Как физические и теоретико-сложностные версии выходят за рамки первоначального утверждения?

Key theories

Сходимость моделей вычислений

Было показано, что машины Тьюринга, лямбда-исчисление Чёрча и рекурсивные функции Гёделя и Эрбрана определяют один и тот же класс функций, и это независимое согласие является основным доказательством, предлагаемым для тезиса.

Статус тезиса, а не теоремы

Поскольку интуитивное понятие эффективной процедуры не формализовано, утверждение не может быть доказано; оно принимается как фундаментальное отождествление, которое позволяет неформальным алгоритмическим аргументам заменять формальные конструкции машин Тьюринга.

Clinical relevance

Тезис позволяет повседневно описывать алгоритмы на высокоуровневом псевдокоде, а не как машины Тьюринга, поскольку любое разумное понятие эффективной процедуры считается эквивалентным Тьюрингу; он также формирует дебаты о том, могут ли физические или квантовые устройства когда-либо вычислять за пределами Тьюринг-вычислимого.

History

В 1936 году Чёрч предложил отождествить эффективную вычислимость с лямбда-определимостью, а Тьюринг независимо обосновал свою модель машины, после чего Тьюринг, Клини и другие доказали эквивалентность этих моделей и рекурсивных функций. Гёдель, изначально скептически настроенный, в конечном итоге счёл анализ Тьюринга убедительным, и объединённое утверждение стало известно как тезис Чёрча — Тьюринга.

Debates

Могут ли физические вычисления превзойти предел Тьюринга?

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

Key figures

• Alonzo Church
• Alan Turing
• Kurt Gödel
• Stephen Kleene

Seminal works

• church1936
• turing1937

Frequently asked questions

Почему это называется тезисом, а не теоремой?

Он связывает формальную модель с неформальной идеей эффективной процедуры, а эта неформальная идея не имеет математического определения, чтобы что-либо доказывать. Веским доказательством является то, что каждая независимая попытка формализовать вычисления привела к одному и тому же классу функций, но эта поддержка является концептуальной, а не доказательством.

Опровергают ли квантовые компьютеры тезис Чёрча — Тьюринга?

Нет. Квантовые компьютеры могут решать некоторые задачи быстрее, но они вычисляют точно тот же класс функций, что и машины Тьюринга, поэтому исходный тезис о том, что вычислимо, остаётся в силе. Они касаются скорее более сильной теоретико-сложностной версии, связанной с эффективностью, а не с вычислимостью.