Вычислимые функции и тезис Чёрча — Тьюринга

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

Definition

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

Scope

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

Core questions

• Что такое машина Тьюринга и как она определяет вычисление?
• Как частично рекурсивные функции генерируются из базовых операций?
• Почему все разумные модели вычислений определяют одни и те же функции?
• Каков статус и значение тезиса Чёрча — Тьюринга?

Key theories

Модель машины Тьюринга

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

Эквивалентность моделей

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

Универсальная машина и перечисление

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

Clinical relevance

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

History

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

Key figures

• Alan Turing
• Alonzo Church
• Stephen Cole Kleene
• Emil Post

Seminal works

• cutland1980
• turing1936
• sipser2013

Frequently asked questions

Некоторые функции невычислимы?

Да. Поскольку программы могут быть перечислены, а функции — нет, аргумент счётности показывает, что большинство функций невычислимы, а конкретные примеры, такие как функция остановки, доказуемо невычислимы. Вычислимость является подлинным ограничением на то, какие функции могут быть оценены алгоритмами.

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

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