Теория алгорифмов

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

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

Предпосылки и интуитивное понятие алгоритма

Понятие алгоритма существовало в математике с древности (алгоритм Евклида для нахождения наибольшего общего делителя, методы решения квадратных уравнений). Однако до начала XX века оно оставалось интуитивным и неформализованным. Потребность в строгом определении возникла в связи с проблемами оснований математики. В 1900 году Давид Гильберт на Втором Международном конгрессе математиков сформулировал 23 проблемы, десятая из которых требовала найти общий метод (алгоритм) для определения разрешимости произвольного диофантова уравнения. В 1928 году Гильберт и Вильгельм Аккерман поставили проблему разрешения (Entscheidungsproblem): существует ли алгоритм, позволяющий по описанию произвольного математического утверждения определить, является ли оно истинным или ложным?

Формализация понятия алгоритма (1930-е годы)

В 1930-х годах сразу несколько математиков независимо друг от друга предложили формальные модели, призванные уточнить интуитивное понятие алгоритма:

• Рекурсивные функции (Курт Гёдель, 1931; Стивен Клини, 1936). Гёдель ввёл понятие примитивно рекурсивных функций, а Клини и Жак Эрбран — общерекурсивных функций. Этот подход описывал алгоритм как функцию, заданную системой рекурсивных уравнений.
• Машина Тьюринга (Алан Тьюринг, 1936). Абстрактная вычислительная машина, состоящая из бесконечной ленты, разделённой на ячейки, и считывающей/записывающей головки, которая может находиться в одном из конечного множества состояний. Машина Тьюринга стала одной из самых наглядных и влиятельных моделей.
• Лямбда-исчисление (Алонзо Чёрч, 1936). Формальная система, основанная на понятии функции и её применения. Чёрч использовал её для доказательства неразрешимости проблемы разрешения.
• Нормальные алгорифмы Маркова (Андрей Андреевич Марков, 1951). Советский математик А. А. Марков разработал свою модель, основанную на подстановках слов в алфавите. Эта модель оказалась особенно удобной для изучения алгоритмических проблем в алгебре и логике.

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

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

Основные модели алгорифмов

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

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

Нормальные алгорифмы Маркова

Нормальный алгорифм (НА) — это модель, оперирующая со строками (словами) в конечном алфавите. Он задаётся упорядоченным списком подстановок вида α → β (или α → ·β для заключительной подстановки). Процесс применения НА к исходному слову заключается в следующем:

1. Просматривается список подстановок слева направо.
2. Находится первая подстановка, левая часть которой α входит в обрабатываемое слово.
3. Первое вхождение α в слово заменяется на β.
4. Если подстановка была заключительной (с точкой), процесс останавливается. Иначе — возврат к шагу 1.

Если ни одна подстановка не применима, процесс останавливается. Нормальные алгорифмы Маркова являются универсальной моделью, эквивалентной машине Тьюринга.

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

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

Ключевые понятия и результаты

Алгоритмическая разрешимость и неразрешимость

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

Проблема остановки (Halting problem) — одна из самых известных алгоритмически неразрешимых задач. Она заключается в том, чтобы по описанию произвольной машины Тьюринга и её входным данным определить, остановится ли она когда-нибудь. Алан Тьюринг в 1936 году доказал, что общего алгоритма для решения этой задачи не существует. Доказательство строится методом от противного и использует диагонализацию.

Десятая проблема Гильберта — ещё один классический пример. В 1970 году Юрий Матиясевич, опираясь на работы Мартина Дэвиса, Хилари Патнема и Джулии Робинсон, доказал, что не существует алгоритма, который бы определял, имеет ли произвольное диофантово уравнение целочисленные решения. Эта задача также алгоритмически неразрешима.

Вычислимость и сложность

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

• Класс P (polynomial time) — задачи, решаемые за полиномиальное время (считаются «практически разрешимыми»).
• Класс NP (nondeterministic polynomial time) — задачи, решение которых можно проверить за полиномиальное время, но неизвестно, можно ли его найти так же быстро.
• NP-полные задачи — самые сложные задачи из класса NP. Если для одной из них будет найден полиномиальный алгоритм, то все задачи из NP будут решаться за полиномиальное время. Проблема равенства классов P и NP является одной из семи «проблем тысячелетия» Математического института Клэя.

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

Теория алгорифмов имеет фундаментальное значение для всей информатики и математики:

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

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

• Термин «алгоритм» происходит от имени арабского математика аль-Хорезми, жившего в IX веке. В латинском переводе его имя звучало как «Algorithmi».
• Алан Тьюринг предложил свою машину в 1936 году, когда ему было 24 года. Его работа «О вычислимых числах с приложением к проблеме разрешения» считается одним из основополагающих текстов в истории информатики.
• А. А. Марков создал свою теорию нормальных алгорифмов в 1947–1951 годах, работая в Московском государственном университете. Его подход отличался строгостью и был ориентирован на применение в математической лингвистике и алгебре.
• Проблема остановки тесно связана с парадоксом брадобрея и другими логическими парадоксами, что подчёркивает глубокую связь между теорией алгоритмов и основаниями математики.

Источники

1. Марков А. А., Нагорный Н. М. Теория алгорифмов. — М.: Наука, 1984.
2. Тьюринг А. М. Может ли машина мыслить? — М.: Государственное издательство физико-математической литературы, 1960.
3. Клини С. К. Введение в метаматематику. — М.: Издательство иностранной литературы, 1957.
4. Минский М. Вычисления и автоматы. — М.: Мир, 1971.
5. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. — М.: Вильямс, 2002.