Теорема Чёрча — Тьюринга¶

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

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

¶Предпосылки и проблема разрешения

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

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

В 1936 году американский математик Алонзо Чёрч предложил формальное определение вычислимости через λ-исчисление (лямбда-исчисление) и понятие рекурсивных функций. Он показал, что класс λ-определимых функций совпадает с классом общерекурсивных функций, введённых Куртом Гёделем и Жаком Эрбраном. Чёрч сформулировал тезис, согласно которому любая интуитивно вычислимая функция является общерекурсивной. На основе этого тезиса он доказал неразрешимость проблемы разрешения для логики первого порядка.

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

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

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

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

¶Формальные определения

¶Машина Тьюринга

Машина Тьюринга — это абстрактный автомат, состоящий из:

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

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

¶λ-исчисление и рекурсивные функции

В λ-исчислении вычислимость определяется через правила редукции (подстановки) термов. Функция называется λ-определимой, если она может быть представлена в виде λ-терма. Класс общерекурсивных функций строится из базовых (нуль, функция следования, проекции) с помощью операций композиции, примитивной рекурсии и минимизации.

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

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

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

¶Неразрешимость проблем

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

¶Теория вычислимости

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

¶Физический тезис Чёрча — Тьюринга

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

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

¶Интуитивное понятие алгоритма

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

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

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

¶Квантовые вычисления

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

¶Применение в информатике

¶Теория алгоритмов

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

¶Языки программирования

Все современные языки программирования общего назначения (C, Python, Java, Haskell) являются тьюринг-полными, то есть их вычислительная мощность эквивалентна машине Тьюринга. Это означает, что любой алгоритм, реализуемый на одном языке, может быть реализован на любом другом тьюринг-полном языке.

¶Искусственный интеллект

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

¶Источники

• Чёрч А. «A note on the Entscheidungsproblem» (1936)
• Тьюринг А. «On Computable Numbers, with an Application to the Entscheidungsproblem» (1936)
• Клини С. К. «Введение в метаматематику» (1952)
• Минский М. «Вычисления и автоматы» (1967)
• Хопкрофт Дж., Мотвани Р., Ульман Дж. «Введение в теорию автоматов, языков и вычислений» (2001)
• Соловьёв В. Д. «Теория вычислимости» (2005)