О невычислимой функции

Что такое невычислимая функция и как она говорит нам о границах познания?

Интуитивно хочется верить, что любую функцию можно запрограммировать — дать ей вход, дождаться ответа. Но в реальности существует класс функций, которые нельзя вычислить никаким алгоритмом. Вообще. Даже если дать бесконечно много времени.

Типичный пример — функция Busy Beaver, но она растёт столь стремительно, что кажется далёкой от жизни. Гораздо интереснее функция, поведение которой можно себе представить — медленно растущая и при этом невычислимая. Её мы и разберём.

Представим: дана задача — напечатать число n. Самый примитивный способ — print(n). Но если число огромное, можно схитрить, использовать циклы или свойства числа. Например:

print(1);
for i := 1 to 1000000 do print(0)

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

Возникает естественный вопрос: какая самая короткая программа, которая печатает заданное число n? Обозначим длину этой программы через f(n).

И вот ключ: функция f(n) — невычислима. То есть невозможно написать программу, которая по числу n вычислит f(n).

Почему?

Допустим, мы смогли бы её вычислить. Тогда можно написать программу, которая находит наименьшее число, которое нельзя напечатать программой короче m символов. Такая программа существует — ведь программ ограниченной длины конечное количество, а чисел бесконечно много.

Теперь добавим к этой программе ещё немного кода — скажем, 100 символов — и попросим её напечатать g(K+100) — то самое "непечатаемое" число. Программа длиной меньше K+100 напечатала число, которое не должна была уметь напечатать. Противоречие. Значит, наша исходная гипотеза — о вычислимости f(n) — ложна.

Этот аргумент перекликается с парадоксом Берри: "наименьшее число, которое нельзя описать менее чем двадцатью словами" — а ведь сама фраза состоит из меньше чем двадцати слов.

Функция f(n) медленно растёт. Прямое распечатывание числа даёт простой, но не оптимальный вариант. Иногда кто-то найдёт программу, которая делает это короче. Но можем ли мы быть уверены, что нет ещё более короткой? Возможно, какая-то программа длиной в 800 символов уже запущена, мы видим её код, но не знаем, остановится ли она. Если бы мы могли это предсказать — мы бы могли вычислять f(n). Но мы не можем. И в этом — краеугольный камень всей теории алгоритмов.

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

Этот результат говорит не просто о математике. Он говорит о границах, за которые не может пройти даже идеальная машина. Даже если мы точно знаем её алгоритм. Мы можем наблюдать за работой программы, видеть её шаги, понимать логику, но не знать финала.

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

Из телеграмма канала "Математика не для всех".