Том 22. Сон разума. Математическая логика и ее парадоксы

Факториал — это пример функции, вычислить значение которой теоретически очень просто, однако на практике компьютеры пасуют перед этой задачей. Как мы уже отмечали в предыдущей главе, все рекурсивные функции являются вычислимыми. Напомним, что функция является рекурсивной, если значение f(n) можно вычислить на основе значений, которые принимает эта функция для чисел, меньших n. Факториал — это классический пример рекурсивной функции, так как если мы хотим вычислить 4! = 1·2·3·4, мы можем сначала найти произведение 1·2·3, а затем умножить его на 4. Но что представляет собой произведение 1·2·3? Оно равно 3! таким образом, если известно значение 3! то чтобы найти 4! достаточно одной операции. В общем случае n! = (n — 1)!·n — это доказывает, что факториал является рекурсивной, а следовательно, и вычислимой функцией. Для машины Тьюринга, способной работать бесконечное время, вычисление n! не представляет трудностей. Но на практике значения факториала возрастают столь быстро, что с ними вскоре становится невозможно работать.

График, показывающий рост значений факториала.

Предыдущий пример был бы не более чем любопытным фактом, если бы факториал не описывал число перестановок элементов конечных множеств, то есть число способов, которыми можно упорядочить их элементы. Так, фразы «3! = 6» и «множество {1, 2, 3} можно записать шестью разными способами (123, 132, 213, 231, 312 и 321)» содержат одинаковую информацию. Так как примитивный метод решения многих задач, схожих с задачей коммивояжера, требует последовательного перебора всех элементов множества, которое может быть достаточно большим, то скорость, с которой возрастают значения факториала, имеет фатальные последствия.

* * *

ИЗОБРЕТАТЕЛЬ ШАХМАТ

По легенде, персидский царь хотел наградить изобретателя шахмат и подарить ему все, что он пожелает. Тогда мудрец удивил царя просьбой, которая показалась скромной: он хотел получить одно зерно за первую клетку доски, два — за вторую, четыре — за третью и т. д. — на каждой клетке доски должно было находиться в два раза больше зерен, чем на предыдущей. Эта просьба показалась царю насмешкой, и он, рассерженный, повелел слугам немедленно исполнить просьбу мудреца и выслать ему столько зерна, сколько тот просил. Каково же было его удивление, когда один из советников на следующий день сообщил ему, что для этого не хватит зерна в амбарах всего мира. Функция, принимавшая значения 1, 2, 4, 8… возрастала столь быстро, что общее число зерен составило 18446744073 709551615.

* * *

В одном из простых определений сложными называются задачи, решение которых требует выполнения сопоставимого числа операций, а простыми считаются те, которые разрешимы не только с теоретической, но и с практической точки зрения, то есть в разумное время. Эти задачи часто обозначаются буквой Р (по первой букве английского слова «полином»), так как число операций для их решения примерно равно некоторому многочлену от времени выполнения.

Ученые заметили, что существуют задачи, найти решение которых очень сложно, а подтвердить его правильность относительно просто. Вернемся к примеру с отелем из главы 2, который на этот раз содержит конечное число комнат. Предположим, что группа из четырехсот человек хочет остановиться в отеле в те дни, когда там будет свободно всего сто номеров. Выбрать сто человек из четырехсот, не следуя какому-либо критерию, очень просто, однако заявка от группы сопровождалась одной странной просьбой: некоторые путешественники настолько не ладили друг с другом, что их нельзя было размещать в соседних номерах. Не стоит и думать, что эту задачу можно решить перебором всех возможных выборок ста человек из четырехсот, но при этом для любого предложенного решения достаточно будет подтвердить, что никакие два путешественника, которые не ладят друг с другом, не будут поселены в соседние номера. С этой задачей сможет справиться администратор отеля даже без помощи компьютера всего за несколько часов. Такие задачи, которые сложно решить, но легко проверить, математики относят к классу NP.