Вычислимость: функции, которые не сможет посчитать ни один компьютер

Задач на свете строго больше, чем программ, — поэтому какие-то задачи обречены остаться без решения.

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

Программ меньше, чем задач

Начнём с подсчёта. Каждая программа — это конечный текст, строка символов. Все возможные тексты можно пронумеровать: первый, второй, третий... Их бесконечно много, но это счётная бесконечность, как у натуральных чисел.

А сколько существует функций, скажем, из натуральных чисел в «да/нет»? Георг Кантор доказал, что таких функций несчётно много — их строго больше, чем натуральных чисел, а значит, больше, чем программ. Вывод неумолим: почти все функции невычислимы просто потому, что программ на всех не хватает. Вычислимые функции — редкие островки в океане невозможного.

Это не абстракция: конкретные примеры

Можно возразить: «ну и что, эти невычислимые функции наверняка какие-то искусственные». Нет. Вот вполне осмысленные задачи, которые доказанно неразрешимы.

Функция остановки

Функция halts(p), которая по программе p говорит, завершится та или зациклится. Как мы знаем из проблемы остановки, такой функции не существует — а ведь вопрос абсолютно понятный.

Усердный бобёр (busy beaver)

Функция $BB(n)$ отвечает: какое наибольшее число шагов может сделать машина Тьюринга из $n$ состояний, прежде чем остановиться (среди тех, что вообще останавливаются)? Звучит безобидно, но эта функция растёт быстрее любой вычислимой функции и потому невычислима. Известно, что $BB(5) = 47\,176\,870$, а вот значение $BB(6)$ уже превосходит всё мыслимое — его невозможно вычислить никаким алгоритмом.

Число Чейтина

Грегори Чейтин определил число $\Omega$ — вероятность того, что случайно собранная программа когда-нибудь остановится. Это конкретное число между 0 и 1, у него есть точные цифры после запятой. Но вычислить эти цифры нельзя: знание $\Omega$ было бы равносильно решению проблемы остановки.

Чем «невычислимо» отличается от «долго»

Важно не путать две разные вещи:

Невычислимость — это не про скорость и не про мощность железа. Дайте машине вечность, бесконечную память, квантовый процессор — невычислимую функцию она всё равно не посчитает. Это граница самого понятия «вычисление».

Почему нельзя «приблизиться» к ответу

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

Это объясняет, почему невычислимость так коварна на практике. Она не выглядит как стена с табличкой «тупик». Она выглядит как программа, которая всё думает и думает, и вы не можете отличить «скоро закончит» от «не закончит никогда». Именно поэтому компиляторы не предупреждают вас обо всех бесконечных циклах: в общем случае это потребовало бы решить проблему остановки.

Где невычислимость встречается в жизни

Может показаться, что всё это — игры теоретиков. Но границы вычислимого упираются в инженерную реальность постоянно:

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

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

Зачем это знать

Понимание вычислимости спасает от погони за миражами. Нельзя написать программу, которая по любому коду докажет его корректность; нельзя создать анализатор, ловящий все возможные ошибки; нельзя автоматически решить любую математическую гипотезу. Это не лень программистов — это теоремы. Зная карту невозможного, инженеры тратят силы там, где решение существует, и строят приближённые методы там, где точного ответа быть не может. Граница вычислимого — одно из самых глубоких открытий XX века, и оно из чистой логики, а не из физики.