Теория вычислений

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

  • Университет
  • 25 мин
  • 10 вопросов
  • Урок 57 из 59

В этом уроке ты узнаешь

  • Строить детерминированный конечный автомат для языка и прослеживать его работу на словах
  • Читать регулярные выражения и доказывать нерегулярность языка с помощью леммы о накачке
  • Объяснять работу машины Тьюринга, неразрешимость проблемы остановки и разницу между P и NP

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

Конечные автоматы

Детерминированный конечный автомат (ДКА)Определение

Машина с конечным числом состояний, читающая вход символ за символом. Для каждого символа функция переходов однозначно задаёт новое состояние; если по окончании слова автомат находится в допускающем состоянии, слово принимается. Вся его память — текущее состояние, «считать» он не умеет.

M = (Q, Σ, δ, q₀, F)δ: Q × Σ → Q

Где

Q
конечное множество состояний
Σ
входной алфавит (например, {0, 1})
δ
функция переходов
q₀, F
начальное состояние и множество допускающих состояний

Пример 1: двоичные числа, кратные 3

Задача

Построй ДКА, принимающий двоичные числа, кратные 3, и проследи его работу на слове 1001.

Показать решениеСкрыть решение

Решение

Состояние — остаток от деления прочитанного числа на 3: Q = {0, 1, 2}, q₀ = 0, F = {0}.
Дописывание бита b превращает число x в 2x + b, поэтому δ(r, b) = (2r + b) mod 3.
1001: 0 →(1) 1 →(0) 2 →(0) 4 mod 3 = 1 →(1) 3 mod 3 = 0 → принято.
Проверка: 1001₂ = 9 = 3 · 3 ✓. Всего 3 состояния хватает для чисел любой длины.

Недетерминированный автомат (НКА) может по одному символу перейти сразу в несколько состояний и принимает слово, если принимает «хотя бы один путь». Он не мощнее ДКА: построение подмножеств превращает НКА с n состояниями в ДКА не более чем с 2ⁿ состояниями. Этот взрыв бывает реальным: язык «третий символ с конца — 1» НКА распознаёт с 4 состояниями, а ДКА — минимум с 8.

Python
import re

def div3(bits):
    state = 0
    for b in bits:
        state = (2 * state + int(b)) % 3
    return state == 0

for s in ['0', '11', '110', '111', '1001', '1010']:
    print(s, int(s, 2), div3(s))

pattern = '(0|1)*1(0|1)(0|1)'
for s in ['0100', '0011', '111', '10']:
    print(s, bool(re.fullmatch(pattern, s)))
print(bool(re.fullmatch('[0-9]{4}-[0-9]{2}-[0-9]{2}', '2026-09-27')))
Ожидаемый результат
0 0 True
11 3 True
110 6 True
111 7 False
1001 9 True
1010 10 False
0100 True
0011 False
111 True
10 False
True
div3 — это и есть ДКА: одна переменная (состояние) и формула перехода. Затем модуль re проверяет регулярное выражение «третий символ с конца — 1» и формат даты ISO; внутри re работает, превращая выражение в автомат.

Чтобы читать дальше, зарегистрируйся бесплатно

Остальные разделы урока, тест и заметки открываются с аккаунтом Educora. Регистрация занимает минуту, а прогресс сохраняется на всех твоих устройствах.

Регулярные выражения и их пределы

Регулярное выражение строится тремя операциями: объединение a|b, конкатенация ab и звезда Клини a* (ноль или более повторений). Теорема Клини: регулярные выражения и конечные автоматы описывают один и тот же класс языков — регулярные языки. На этой теории основаны шаблоны поиска, лексические анализаторы (первый этап компилятора) и проверка форм.

L регулярен ⇒ ∃ p: ∀ w ∈ L, |w| ≥ p: w = xyz, |xy| ≤ p, |y| ≥ 1, xyⁱz ∈ L ∀ i ≥ 0

Где

p
длина накачки (число состояний автомата)
y
непустая часть, которую можно повторять или удалять сколько угодно

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

Пример 2: aⁿbⁿ — нерегулярный язык

Задача

Докажи, что язык L = {aⁿbⁿ : n ≥ 0} (например, aabb, aaabbb) не регулярен.

Показать решениеСкрыть решение

Решение

Предположим противное: L регулярен и p — длина накачки.
Возьмём w = aᵖbᵖ: w ∈ L, |w| = 2p ≥ p.
Так как |xy| ≤ p, x и y состоят только из букв a: y = aᵏ, k ≥ 1.
i = 2: xy²z = aᵖ⁺ᵏbᵖ — букв a больше, чем b, значит, xy²z ∉ L.
Противоречие → L не регулярен. Смысл: конечной памятью нельзя «запомнить» произвольное n; поэтому регулярным выражением не проверить правильность скобок — нужен стек.
Класс языков (иерархия Хомского)МашинаПример
Регулярныеконечный автоматдвоичные числа, кратные 3, шаблон email
Контекстно-свободныеавтомат с магазинной памятью (стеком)aⁿbⁿ, правильные скобки, синтаксис языков программирования
Контекстно-зависимыелинейно ограниченный автоматaⁿbⁿcⁿ
Рекурсивно перечислимыемашина Тьюрингаостанавливающиеся программы
Каждый класс входит в следующий: сверху вниз память машины растёт — нет памяти, стек, ограниченная лента, бесконечная лента.

Машина Тьюринга и разрешимость

Машина Тьюринга состоит из бесконечной ленты, читающей и пишущей головки и конечной таблицы переходов: δ(состояние, символ) = (новое состояние, записываемый символ, влево/вправо). Эта простая модель вычисляет всё, что может вычислить любой современный компьютер. Согласно тезису Чёрча — Тьюринга, функции, вычислимые «алгоритмом», — это ровно функции, вычислимые машиной Тьюринга; Python и JavaScript в этом смысле «тьюринг-полны».

СостояниеЧитаетПишетСдвигНовое состояние
right0 / 1то жеRright
right__Lcarry
carry10Lcarry
carry0 / _1–halt
Машина Тьюринга, прибавляющая 1 к двоичному числу (_ — пустая клетка): сначала идём к правому краю, затем справа налево превращаем единицы в нули, а первый 0 (или пустую клетку) — в 1.
Python
def increment(tape):
    tape = ['_'] + list(tape) + ['_']
    head, state, steps = 1, 'right', 0
    while state != 'halt':
        symbol = tape[head]
        if state == 'right':
            if symbol == '_':
                state, head = 'carry', head - 1
            else:
                head += 1
        elif state == 'carry':
            if symbol == '1':
                tape[head], head = '0', head - 1
            else:
                tape[head], state = '1', 'halt'
        steps += 1
    return ''.join(tape).strip('_'), steps

for t in ['1011', '111', '1000']:
    print(t, '+ 1 =', *increment(t))
Ожидаемый результат
1011 + 1 = 1100 8
111 + 1 = 1000 8
1000 + 1 = 1001 6
Симуляция машины из таблицы; последнее число — количество шагов. В случае 111 + 1 перенос доходит до пустой клетки слева, и число удлиняется на одну клетку: 1000.

Пример 3: проблема остановки неразрешима

Задача

Докажи, что не существует функции halts(P, x), которая для любой программы P и входа x всегда правильно отвечает на вопрос «остановится ли когда-нибудь P(x)?».

Показать решениеСкрыть решение

Решение

Предположим противное: halts существует. Напишем программу:
D(P): если halts(P, P) истинно — зациклиться; иначе остановиться.
Запустим D на самой себе — D(D):
• Если D(D) останавливается, то halts(D, D) истинно, и D зацикливается — не останавливается. Противоречие.
• Если D(D) не останавливается, то halts(D, D) ложно, и D останавливается. Снова противоречие.
Значит, halts не существует (Тьюринг, 1936). Это диагональный метод Кантора. Следствие: ни антивирус, ни компилятор не могут точно ответить «зависнет ли?» для всех программ.

P и NP

P — задачи, решаемые за полиномиальное время (например, O(n³)): сортировка, кратчайшие пути, MST. NP — задачи, предложенное решение (сертификат) которых можно проверить за полиномиальное время: судоку, раскраска графа в 3 цвета, рюкзак, сумма подмножества. Очевидно, P ⊆ NP. NP-полные задачи — «самые трудные» в NP: полиномиальный алгоритм для одной из них решил бы весь класс NP. Первой NP-полной задачей стала выполнимость булевых формул (SAT, теорема Кука — Левина, 1971).

Python
from itertools import combinations

nums, target = [3, 34, 4, 12, 5, 2], 9
checked, found = 0, None
for size in range(1, len(nums) + 1):
    for subset in combinations(nums, size):
        checked += 1
        if found is None and sum(subset) == target:
            found = (subset, checked)
print('found', found[0], 'after checking', found[1], 'subsets')
print('all non-empty subsets:', checked, '| for n = 60:', 2 ** 60 - 1)
print('verify certificate (4, 5):', sum((4, 5)) == target)
Ожидаемый результат
found (4, 5) after checking 17 subsets
all non-empty subsets: 63 | for n = 60: 1152921504606846975
verify certificate (4, 5): True
Сумма подмножества: полный перебор для поиска решения просматривает 2ⁿ − 1 подмножеств (≈ 1,15 · 10¹⁸ при n = 60), а проверка готового ответа — одно суммирование. В этом и состоит вопрос P = NP: всякая ли задача, которую легко проверить, также легко решается?

Запомни

  • ДКА = (Q, Σ, δ, q₀, F); его память — только состояние; НКА не мощнее, но может быть компактнее до 2ⁿ раз.
  • Регулярные выражения и конечные автоматы описывают одни и те же языки; aⁿbⁿ не регулярен (лемма о накачке).
  • Машина Тьюринга моделирует любой алгоритм (тезис Чёрча — Тьюринга).
  • Проблема остановки неразрешима: диагональный аргумент приводит к противоречию.
  • P — быстро решаемые, NP — быстро проверяемые задачи; NP-полные (SAT) — самые трудные; P = NP — открытый вопрос.
Заметил ошибку или неточность в уроке?

Проверь себя

Вопросов: 10. Каждый правильный ответ приносит XP.

Вопрос 1 / 10

Вопрос 1 / 10. Какое слово примет ДКА «двоичные числа, кратные 3» (δ(r, b) = (2r + b) mod 3)?