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

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

История и происхождение

Предпосылки возникновения

В начале XX века, в рамках программы Гильберта по формализации математики, возникла необходимость чётко определить, какие задачи могут быть решены механически, без участия человеческой интуиции. В 1928 году Давид Гильберт и Вильгельм Аккерман поставили проблему разрешения (Entscheidungsproblem): существует ли алгоритм, который для любого утверждения формальной логики определяет, является ли оно общезначимым? Для ответа на этот вопрос требовалось формальное определение понятия «алгоритм» или «эффективная процедура».

Формулировки Чёрча и Тьюринга

В 1936 году независимо друг от друга были предложены две ключевые формализации:

• Алонзо Чёрч (США) ввёл понятие рекурсивных функций (λ-определимых функций в лямбда-исчислении). Он показал, что проблема разрешения для логики первого порядка неразрешима, если принять, что класс рекурсивных функций исчерпывает все интуитивно вычислимые функции. Это утверждение стало известно как тезис Чёрча.
• Алан Тьюринг (Великобритания) предложил абстрактную вычислительную машину (машину Тьюринга), которая выполняет элементарные действия над символами на бесконечной ленте. Он показал, что класс функций, вычислимых на такой машине, совпадает с классом рекурсивных функций Чёрча. Тьюринг также сформулировал свой тезис: «всякая интуитивно вычислимая функция вычислима на машине Тьюринга».

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

Формулировка и сущность

Тезис Чёрча — Тьюринга обычно формулируется в двух вариантах:

1. Классическая (математическая) формулировка: Функция является эффективно вычислимой (в интуитивном смысле) тогда и только тогда, когда она вычислима на машине Тьюринга.
2. Физическая (или расширенная) формулировка: Любой вычислительный процесс, который может быть реализован в физической вселенной, может быть смоделирован на машине Тьюринга (при условии, что доступны неограниченные ресурсы памяти и времени).

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

Статус и обоснование

Не является теоремой

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

Эмпирические подтверждения

Несмотря на отсутствие формального доказательства, тезис имеет мощную эмпирическую поддержку:

• Эквивалентность всех известных моделей: Все предложенные за 80 лет формальные модели вычислимости (рекурсивные функции, машины Тьюринга, лямбда-исчисление, нормальные алгоритмы Маркова, машины Поста, клеточные автоматы, RAM-машины) оказались эквивалентными.
• Отсутствие контрпримеров: За всю историю не было найдено ни одного примера функции, которая была бы интуитивно вычислимой, но не вычислимой на машине Тьюринга.
• Практика программирования: Современные языки программирования (C++, Python, Java) являются тьюринг-полными, то есть могут вычислять всё, что вычислимо на машине Тьюринга. Ни один реальный язык программирования не вышел за эти рамки.

Следствия и значение

Проблема разрешения (Entscheidungsproblem)

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

Проблема остановки

Тезис лежит в основе доказательства неразрешимости проблемы остановки (halting problem): не существует алгоритма, который мог бы определить, завершится ли выполнение произвольной программы на машине Тьюринга. Это является одним из фундаментальных ограничений вычислимости.

Теория сложности вычислений

Тезис Чёрча — Тьюринга является основой для классификации задач по классам сложности (P, NP, PSPACE и др.). Он позволяет говорить о «вычислимости за полиномиальное время» как о едином стандарте эффективности, не зависящем от конкретной модели вычислений.

Критика и альтернативы

Гипервычисления

Некоторые исследователи (например, Джек Коупленд) предлагают концепцию гипервычислений — вычислений, выходящих за рамки возможностей машины Тьюринга. К таким гипотетическим устройствам относятся:

• Машины с оракулом: Машины Тьюринга, которые могут получать ответы на неразрешимые вопросы из внешнего источника.
• Машины с бесконечной памятью и временем: Машины, которые могут выполнять бесконечное число шагов за конечное время (например, машины Зенона).
• Квантовые компьютеры: Хотя квантовые компьютеры могут решать некоторые задачи быстрее, они, как считается, не могут решать неразрешимые для машины Тьюринга задачи (тезис Чёрча — Тьюринга в квантовом варианте обычно считается верным).

Квантовый тезис Чёрча — Тьюринга

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

Мозг и интуиция

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

Интересные факты

• Тезис Чёрча — Тьюринга часто называют «тезисом Тьюринга» или «тезисом Чёрча», хотя в русскоязычной литературе чаще используется двойное название.
• Тезис является основой для понятия тьюринг-полноты — свойства языка программирования или системы быть способной вычислить любую функцию, вычислимую на машине Тьюринга.
• В 2012 году Алан Тьюринг и Алонзо Чёрч были посмертно награждены премией Тьюринга (ACM) за их вклад в теорию вычислимости.

Источники

• Чёрч, А. «Введение в математическую логику». — М.: ИЛ, 1960.
• Тьюринг, А. «О вычислимых числах с приложением к проблеме разрешения» (1936).
• Мендельсон, Э. «Введение в математическую логику». — М.: Наука, 1976.
• Успенский, В. А. «Теорема Гёделя о неполноте». — М.: Наука, 1982.
• Коупленд, Дж. «Тезис Чёрча — Тьюринга» // Стэнфордская философская энциклопедия.