Как бы быстро ни работали компьютеры, существуют задачи, которые не решит никакая программа, — и это доказанный факт. Теория вычислений ищет ответы на три вопроса: что такое «вычисление», что вообще можно вычислить и что можно вычислить эффективно? Ответы проходят через простые модели — конечный автомат и машину Тьюринга, а результаты применяются везде: от компиляторов до криптографии.
Конечные автоматы
Детерминированный конечный автомат (ДКА)Определение
Машина с конечным числом состояний, читающая вход символ за символом. Для каждого символа функция переходов однозначно задаёт новое состояние; если по окончании слова автомат находится в допускающем состоянии, слово принимается. Вся его память — текущее состояние, «считать» он не умеет.
Где
- Q
- конечное множество состояний
- Σ
- входной алфавит (например, {0, 1})
- δ
- функция переходов
- q₀, F
- начальное состояние и множество допускающих состояний
Пример 1: двоичные числа, кратные 3
Задача
Построй ДКА, принимающий двоичные числа, кратные 3, и проследи его работу на слове 1001.
Показать решениеСкрыть решение
Решение
Дописывание бита 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.
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* (ноль или более повторений). Теорема Клини: регулярные выражения и конечные автоматы описывают один и тот же класс языков — регулярные языки. На этой теории основаны шаблоны поиска, лексические анализаторы (первый этап компилятора) и проверка форм.
Где
- p
- длина накачки (число состояний автомата)
- y
- непустая часть, которую можно повторять или удалять сколько угодно
Лемма о накачке: длинное слово обязательно проходит некоторое состояние дважды (принцип Дирихле), и этот цикл можно повторять сколько угодно раз.
Пример 2: aⁿbⁿ — нерегулярный язык
Задача
Докажи, что язык L = {aⁿbⁿ : n ≥ 0} (например, aabb, aaabbb) не регулярен.
Показать решениеСкрыть решение
Решение
Возьмём 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 в этом смысле «тьюринг-полны».
| Состояние | Читает | Пишет | Сдвиг | Новое состояние |
|---|---|---|---|---|
| right | 0 / 1 | то же | R | right |
| right | _ | _ | L | carry |
| carry | 1 | 0 | L | carry |
| carry | 0 / _ | 1 | – | halt |
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
Пример 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).
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
Запомни
- ДКА = (Q, Σ, δ, q₀, F); его память — только состояние; НКА не мощнее, но может быть компактнее до 2ⁿ раз.
- Регулярные выражения и конечные автоматы описывают одни и те же языки; aⁿbⁿ не регулярен (лемма о накачке).
- Машина Тьюринга моделирует любой алгоритм (тезис Чёрча — Тьюринга).
- Проблема остановки неразрешима: диагональный аргумент приводит к противоречию.
- P — быстро решаемые, NP — быстро проверяемые задачи; NP-полные (SAT) — самые трудные; P = NP — открытый вопрос.