Что компьютер может и чего не может

Теория вычислений отвечает на вопрос, который старше любого языка программирования: что в принципе можно вычислить?

Теория вычислений — раздел информатики, изучающий, какие задачи решаемы алгоритмически, какими ресурсами и какими абстрактными машинами.

Зачем теоретику и практику одно и то же

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

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

Абстрактные машины как линейка сложности

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

модель                  память              что распознаёт
--------------------------------------------------------------
конечный автомат        фиксированная       регулярные языки
магазинный автомат      стек                КС-языки
машина Тьюринга         бесконечная лента   всё вычислимое

Каждая следующая модель строго мощнее предыдущей. Конечный автомат не умеет считать до произвольного числа, потому что у него нет памяти под счётчик. Стек добавляет ровно одну степень свободы — и этого хватает на вложенные скобки, но не на проверку, что число открывающих, закрывающих и ещё каких-то символов совпадает. Лента машины Тьюринга снимает все ограничения по памяти — и она оказывается пределом: ничто разумное не вычисляет больше, чем машина Тьюринга. Это утверждение — тезис Чёрча-Тьюринга, к нему мы придём в седьмом разделе.

Как работает под капотом

Почему вообще можно доказать, что задача неразрешима? Ключ — в счётном и несчётном. Программ — счётное число: каждую можно записать как конечную строку, а строки нумеруются. А вот функций из строк в «да/нет» — несчётно много (это показывает диагональный аргумент Кантора). Значит, функций больше, чем программ, и почти все функции невычислимы. Мы не просто верим в это — в разделе о разрешимости мы построим конкретную невычислимую задачу диагональным методом.

Маленькая иллюстрация счётности строк: их действительно можно перечислить.

alphabet = "ab"

def strings_up_to(length):
    result = [""]
    current = [""]
    for _ in range(length):
        nxt = []
        for s in current:
            for c in alphabet:
                nxt.append(s + c)
        result += nxt
        current = nxt
    return result

for s in strings_up_to(2):
    print(repr(s))

Вывод:

''
'a'
'b'
'aa'
'ab'
'ba'
'bb'

Перечисление никогда не остановится, но каждая строка рано или поздно появится под конечным номером. Это и означает счётность.

Частые ошибки

«Неразрешимо = очень долго». Нет. NP-трудные задачи решаемы (просто медленно), а неразрешимые — не решаемы вообще, сколько бы времени вы ни дали. Это разные оси: разрешимость и сложность.

«Современные ИИ обойдут эти пределы». Любая программа, любая нейросеть, любой квантовый алгоритм — всё это не мощнее машины Тьюринга в смысле вычислимости. Квантовый компьютер ускоряет некоторые задачи, но не делает неразрешимое разрешимым.

«Теория оторвана от практики». Каждый regex, который вы пишете, компилируется в конечный автомат. Каждый компилятор использует КС-грамматику. Граница «регулярно / не регулярно» объясняет, почему HTML нельзя корректно распарсить регуляркой.

Итог

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