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

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

История возникновения

Проблема формализации понятия алгоритма стала центральной в математике первой половины XX века. До 1930-х годов термин «алгоритм» использовался интуитивно, без строгого определения. Развитие математической логики, работы Давида Гильберта по проблеме разрешения (Entscheidungsproblem) и попытки обоснования оснований математики привели к необходимости чётко определить, какие функции можно считать вычислимыми.

Ключевой вклад в решение этой задачи внесли три исследователя, работавшие независимо друг от друга.

Работы Алонзо Чёрча

В 1936 году американский математик Алонзо Чёрч опубликовал статью «Замечание о проблеме разрешения», в которой он:

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

Работы Алана Тьюринга

В том же 1936 году британский математик Алан Тьюринг в статье «О вычислимых числах в приложении к проблеме разрешения» предложил принципиально иную модель: машину Тьюринга. Это абстрактное вычислительное устройство, состоящее из бесконечной ленты и головки, которая может читать, записывать символы и перемещаться по ленте в соответствии с конечным набором правил.

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

Работы Эмиля Поста

Независимо от Тьюринга и Чёрча, американский математик Эмиль Пост в 1936 году предложил собственную формализацию вычислимости, основанную на понятии «работы по алгоритму», используя схожие с машиной Тьюринга идеи. Его подход также внёс вклад в формирование единой концепции.

Объединение тезисов

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

Формулировки тезиса

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

Основные версии

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

Эквивалентные модели вычислимости

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

• Машина Тьюринга (классическая и многоленточная).
• λ-исчисление Алонзо Чёрча.
• Рекурсивные функции (Курта Гёделя, Стивена Клини). Любая вычислимая функция может быть определена через композицию, примитивную рекурсию и минимизацию.
• Нормальные алгоритмы Маркова — одна из первых отечественных формализаций алгоритма, разработанная Андреем Марковым-младшим.
• Машина Поста — упрощённая модель, близкая к машине Тьюринга.
• Регистровые машины (Random Access Machine, RAM).
• Языки программирования (все так называемые тьюринг-полные языки — от Fortran и C до Python и Java — эквивалентны по классу задач, которые они могут решить, хотя и различаются по удобству и производительности).

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

Значение и следствия

Для математики и логики

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

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

Для информатики и теории алгоритмов

• Тезис является основой классификации задач по сложности и разрешимости. Все алгоритмически разрешимые задачи образуют класс R (recursive — рекурсивные). Задачи, не имеющие алгоритмического решения (например, проблема остановки), называются алгоритмически неразрешимыми.
• Понятие Тьюринг-полноты широко используется для оценки выразительной силы языков программирования и вычислительных систем. Система считается тьюринг-полной, если на ней можно реализовать любую вычислимую функцию.

Для философии и когнитивных наук

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

Критика и ограничения

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

1. Квантовые вычисления. Возможности квантовых компьютеров основаны на принципах квантовой механики, которые отличаются от классической логики. Хотя сильный тезис утверждает, что квантовые машины не превосходят по классу разрешимых задач классические машины Тьюринга, существуют проблемы (например, факторизация больших чисел с помощью алгоритма Шора), которые квантовые компьютеры могут решить экспоненциально быстрее. Вопрос о том, являются ли такие вычисления «алгоритмическими» в классическом смысле, остаётся открытым.
2. Гиперкомпьютеры и реалистичные модели. Существуют теоретические модели (гиперкомпьютеры), которые могли бы решать алгоритмически неразрешимые задачи. Например, оракульная машина Тьюринга или машина с бесконечным временем работы. Однако эти модели требуют нефизических допущений (например, бесконечной точности измерений или бесконечной памяти), что делает их невозможными в физической реальности.
3. Интуитивное понятие алгоритма. Эмпирическое подтверждение тезиса, хотя и огромное, не является формальным доказательством. В будущем не исключено открытие класса интуитивно вычислимых функций, которые не могут быть формализованы с помощью существующих моделей. Однако за почти сто лет существования тезиса таких контрпримеров не найдено.

Источники

• Church, A. (1936). "An unsolvable problem of elementary number theory". American Journal of Mathematics.
• Turing, A. M. (1936). "On computable numbers, with an application to the Entscheidungsproblem". Proceedings of the London Mathematical Society.
• Kleene, S. C. (1952). Introduction to Metamathematics. D. Van Nostrand.
• Мендельсон, Э. (1984). Введение в математическую логику. М.: Наука.
• Колмогоров, А. Н., & Драгалин, А. Г. (1982). Введение в математическую логику. М.: Изд-во МГУ.
• Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning.