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

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

История

Предыстория и формализация алгоритма

До начала XX века понятие «алгоритм» использовалось в интуитивном смысле — как последовательность действий для решения конкретной арифметической или геометрической задачи. Математики, такие как Евклид (алгоритм Евклида) и Аль-Хорезми, заложили его основы, но строгого определения не существовало. Развитие математической логики в работах Д. Гильберта, А. Чёрча и С. Клини в 1920–1930-х годах привело к необходимости формализовать понятие вычислимости. Программа Гильберта по проверке непротиворечивости математики потребовала точного определения того, что значит «механически решить проблему».

Ключевые работы 1930-х годов

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

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

Проблема останова и неразрешимость

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

В 1936 году Чёрч, независимо от Тьюринга, доказал неразрешимость проблемы разрешимости для логики первого порядка (Entscheidungsproblem). Эти результаты положили начало теории неразрешимых задач.

Развитие в послевоенный период

Во второй половине XX века теория вычислимости развивалась в нескольких направлениях. Появились теория рекурсии (С. Клини, Э. Пост, Д. Роджерс), изучающая иерархии неразрешимых множеств, теория сложности вычислений (С. Кук, Р. Карп, Л. Левин), отделившая вычислимые задачи от сложности их решения, и теория описательной сложности (Р. Фейн, М. Абрамский). Были введены такие понятия, как оракульные машины (машины Тьюринга с внешним источником ответов), индексные множества, степени неразрешимости, m-сводимость и тьюрингова сводимость. В 1970–1980-х годах началось активное применение идей вычислимости в анализе параллельных вычислений, квантовых вычислений и биологических моделях (например, ДНК-вычисления).

Основные модели вычислений

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

Машина Тьюринга (МТ) — абстрактное устройство, состоящее из:

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

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

Лямбда-исчисление

Лямбда-исчисление — формальная система, основанная на абстракции функции и применении (аппликации). Выражение в лямбда-исчислении имеет вид λx.M, обозначающее функцию от аргумента x со значением M. Основные правила — β-редукция (подстановка аргумента в тело функции) и α-конверсия (переименование связанных переменных). Система является тьюринг-полной, то есть эквивалентна по выразительной силе машине Тьюринга.

Рекурсивные функции

Теория рекурсивных функций, развитая Гёделем, Клини и Робинсоном, определяет класс всех функций, которые могут быть получены из базовых (константа zero, функция следования, функции проекции) с помощью композиции, примитивной рекурсии и минимизации (оператора μ-рекурсии). Функции, вычислимые по Тьюрингу, в точности совпадают с частично-рекурсивными функциями — наиболее широким классом.

Другие модели

• Машины Поста — алфавит из двух символов (0 и 1), работа с маркерами в цепочечной структуре.
• Клеточные автоматы (например, игра «Жизнь» Конвея) — хотя не являются алгоритмами в классическом смысле, они универсальны по Тьюрингу при определённых правилах.
• Нормальные алгоритмы Маркова — формальная система для преобразования строк, предложенная советским математиком А. А. Марковым в 1947 году.

Основные понятия и результаты

Вычислимые функции

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

Неразрешимые задачи

Помимо проблемы остановки, к классическим неразрешимым задачам относятся:

• Проблема тождества слов в полугруппах (Пост, 1947);
• Проблема соответствия Поста — задача о сопоставлении двух списков слов;
• Проблема разрешимости логики первого порядка (теорема Чёрча);
• Проблема разрешимости для диофантовых уравнений (десятая проблема Гильберта, решена Матиясевичем в 1970 году);
• Проблема остановки для программ на C, Python и других языках общего назначения (как следствие тьюринг-полноты).

Сводимость и степени неразрешимости

Задача A сводится к задаче B, если решение B позволяет решить A. Основные типы сводимости:

• m-сводимость (по многим единичным) — существует вычислимая функция, преобразующая входы A во входы B;
• тьюрингова сводимость (T-сводимость) — задача A разрешима с помощью оракульной машины, имеющей доступ к задаче B.

На основе T-сводимости строится иерархия степеней неразрешимости (тьюринговых степеней), частично упорядоченных множеств, где каждой задаче сопоставляется её класс эквивалентности.

Теория рекурсии

Раздел изучает свойства множества всех вычислимых функций. Важные результаты:

• Теорема Клини о неподвижной точке — для любой вычислимой функции f существует такая программа p, что программа f(p) решает ту же задачу, что и p.
• Индексные множества — определение свойств вычислимости по индексу (номеру) программы. Например, множество всех индексов программ, останавливающихся на пустом входе, является рекурсивно перечислимым, но не рекурсивным.
• Теорема разрешения для иерархии арифметической — определение степени неразрешимости формул арифметики Пеано (проективные множества).

Классификация задач по сложности

Хотя теория вычислимости отвечает на вопрос о принципиальной разрешимости, теория сложности вычислений изучает ресурсные затраты (время, память) для решения разрешимых задач. Однако в рамках самой теории вычислимости существует иерархия неразрешимых множеств по их «степени сложности» (по тьюринговой степени).

Рекурсивно перечислимые множества

Множество A называется рекурсивно перечислимым (р.п.), если существует машина Тьюринга, перечисляющая его элементы (возможно, с повторениями). Например:

• множество всех программ, завершающихся на пустом входе — р.п.;
• его дополнение (программы, не завершающиеся) не является р.п.;
• диагностическое множество К — множество индексов программ, завершающихся на собственном коде — классический пример р.п. нерекурсивного множества.

Проблема P vs NP

Строго говоря, проблема P ≠ NP относится к теории сложности, а не к вычислимости, так как P и NP — классы разрешимых задач. Тем не менее, она тесно связана: если P = NP, то многие задачи дискретной математики, традиционно считающиеся труднорешаемыми, окажутся вычислимыми за полиномиальное время.

Применение и значение

В математике

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

В информатике

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

В философии

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

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

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

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

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

Источники

• Turing, A. M. (1936). On Computable Numbers, with an Application to the Entscheidungsproblem.
• Church, A. (1936). An Unsolvable Problem of Elementary Number Theory.
• Kleene, S. C. (1967). Mathematical Logic.
• Rogers, H. (1967). Theory of Recursive Functions and Effective Computability.
• Марков, А. А. (1954). Теория алгорифмов.
• Гёдель, К. (1931). О формально неразрешимых предложениях Principia Mathematica и родственных систем.
• Hopcroft, J. E., Ullman, J. D. (1979). Introduction to Automata Theory, Languages, and Computation.
• Sipser, M. (2006). Introduction to the Theory of Computation.