Машины Тьюринга и теория сложности

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

МТ = (Q, Σ, Γ, δ, q₀, q_accept, q_reject): Q — состояния, Σ — входной алфавит, Γ — ленточный алфавит (Σ ⊆ Γ), δ: Q×Γ → Q×Γ×{L,R} — функция переходов. Бесконечная лента, читающая/пишущая головка.

МТ — теоретическая модель компьютера. Тезис Чёрча–Тьюринга: всё, что можно вычислить интуитивно, вычисляет машина Тьюринга.

Классы сложности

P: задачи, решаемые ДМТ за полиномиальное время O(nᵏ).

NP: задачи, решение которых проверяется за полиномиальное время. Эквивалентно: решаются недетерминированной МТ за полиномиальное время.

NP-полные задачи: любая задача из NP полиномиально сводится к ней. SAT (Кук, 1971), Клика, Раскраска, TSP,...

P = NP? Главная открытая проблема Computer Science. Большинство математиков считают P ≠ NP, но доказательства нет.

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

Проблема остановки: нет алгоритма, который для произвольной МТ M и входа w определяет, остановится ли M(w).

Доказательство диагонализацией (Тьюринг, 1936): предполагаем существование алгоритма H(M, w) → {halt, loop}. Строим M*: M*(M) = loop если H(M,M)=halt, и halt иначе. Парадокс при запуске M*(M*).

Теорема Райса: Любое нетривиальное семантическое свойство языков ТМ неразрешимо.

Граница между «разрешимым» и «нет» — фундаментальная граница математики и Computer Science.

Машина Тьюринга: детали и варианты

МТ с несколькими лентами: эквивалентна однолентовой, но может быть квадратично быстрее. Нелинейная МТ: с оракулом; МТ с вероятностным выбором (PTM): вероятностные языки. Классы: P (детерминированно за полиномиальное время), NP (недетерминированно), PSPACE (полиномиальная память), EXPTIME. P ⊆ NP ⊆ PSPACE ⊆ EXPTIME — эти включения доказаны. P ⊊ EXPTIME строго (теорема об иерархии по времени). P ≠ NP — открытая проблема тысячелетия; большинство включений внутри этой цепочки (P⊊NP, NP⊊PSPACE) ещё не доказаны.

Нерешимость задачи остановки (Тьюринг, 1936): дана пара (М, w), остановится ли машина М на входе w? Доказательство диагонализацией — одно из самых изящных в математике. Предположим, H(М, w) = 1 если М останавливается, 0 иначе. Построим D(М) = if H(М, М) then loop else halt. Тогда D(D) — противоречие. Эта техника диагонализации — прямой аналог доказательства Кантора о несчётности ℝ.

Теорема Гёделя и неполнота

Теорема Гёделя о неполноте (1931): Любая непротиворечивая формальная система, содержащая арифметику, содержит истинные, но недоказуемые утверждения. Связь с теорией вычислений: нерешимость задачи остановки ↔ первая теорема неполноты (через кодирование). Утверждение «программа М не останавливается» может быть истинным, но недоказуемым в PA (арифметике Пеано). Теорема Парижа-Харрингтона (1977) — пример арифметического утверждения, истинного, но недоказуемого в PA.

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

Сложность описания и алгоритмическая информация

Кольмогоровская сложность K(x) — длина кратчайшей программы (на фиксированном языке), порождающей x. Случайная строка: K(x) ≈ |x| (несжимаема). Правило Кольмогорова: почти все строки длины n имеют K(x) ≥ n (случайны). Теорема несчётности: K неразрешима — нельзя алгоритмически вычислить K(x) для произвольного x. Связь с энтропией Шеннона: E[K(X)] ≈ H(X) для источника X.

Неразрешимость: проблема останова и её следствия

Проблема останова: Дан ТМ M и вход w, остановится ли M(w)? Неразрешима — диагональный аргумент Тьюринга. Следствия через сведения: проблема пустоты ТМ, проблема эквивалентности ТМ, проблема вхождения в L(M). Теорема Райса: любое нетривиальное свойство языка ТМ неразрешимо. Это мощный инструмент: доказывает неразрешимость без явного сведения.

Сложность и доказуемость: теорема Гёделя

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

Квантовая вычислимость и сложность

Класс BQP: задачи, решаемые квантовым ТМ с ошибкой ≤ 1/3 за полиномиальное время. P ⊆ BQP ⊆ PSPACE. Неизвестно, строгие ли включения. Разложение на множители (Шор): NP ∩ co-NP, в BQP. Поиск (Гровер): O(√N) — квадратичное ускорение по сравнению с классическими O(N). Квантовое превосходство (quantum supremacy): Google (2019) утверждает решение задачи выборки за 200 секунд, на что классическому суперкомпьютеру нужно 10000 лет — спорное, но историческое утверждение.

Оракульные модели и иерархия классов сложности

Оракул A: A-относительный класс P^A содержит задачи, решаемые ТМ с доступом к оракулу A за полиномиальное время. Теорема Бейкера-Гилла-Соловея: существуют оракулы A и B, что P^A = NP^A и P^B ≠ NP^B. Следствие: диагонализация не может решить вопрос P vs NP. Теорема Тоды (Toda, 1991): PH ⊆ P^{#P}. Весь полиномиальный иерархий класс сводится к одному оракулу счёта — решение #P-полной задачи даёт полную мощность PH.

Численный пример: диагонализация и задача остановки

Задача: Доказать нерешимость HALT методом диагонализации (конструктивная иллюстрация на 3 машинах).

Шаг 1: Предположим, существует решающая машина H(M, w): возвращает «да», если M(w) останавливается, «нет» иначе.

Шаг 2: Строим машину D(M): если H(M,M)=«да», то D зацикливается; если H(M,M)=«нет», то D останавливается за 1 шаг.

Шаг 3: Запускаем D(D). Случай A: H(D,D)=«да» (D останавливается на D) → по построению D зацикливается — противоречие. Случай B: H(D,D)=«нет» → D останавливается — противоречие.

Шаг 4: Оба случая невозможны → H не существует → HALT нерешима. Аналогия с Кантором: D — «диагональный» объект, которого нет ни в одной строке перечисления. Теорема Тоды (1991): PH ⊆ P^{#P} — несмотря на то что HALT неразрешима, #P-оракул решает все задачи полиномиальной иерархии, демонстрируя огромную мощность задач счёта.