Игорь Бурдонов

Многомирие

Я не физик, и потому не имею никакого собственного мнения по поводу «физического смысла» этих замечательных теорий о многомирии.

Но, как математику, мне это напомнило одну из «проблем тысячелетия»: P-NP проблему. В одной из интерпретаций она звучит так.

Как известно, машина Тьюринга – это формальная математическая конструкция, призванная математически выразить неформальное понятие алгоритма: всё, что можно вычислить алгоритмически, можно вычислить с помощью машины Тьюринга (эвристический тезис Чёрча-Тьюринга).

Машина Тьюринга устроена до обидного просто: она состоит из ленты и головки.

Бесконечная лента разбита на клетки, в каждой клетке можно записать символ из конечного алфавита. Например, «0» или «1», двух этих символов достаточно, чтобы записать всё, что угодно.

Вначале на ленте записано условие задачи. Для этого достаточно конечного числа клеток, остальные клетки остаются пустыми.

Головка машины – это такой конечный робот, который находится в одной из клеток на ленте. С самого начала – в одной из занятых клеток, например, в самой левой.

Почему робот конечный? Потому что у него конечное множество состояний.

Что робот может делать? За 1 такт времени робот читает символ, записанный той клетке, где он находится, и, в зависимости от прочитанного символа и своего состояния, робот совершает «переход».

Что значит переход? Это значит, во-первых, что робот меняет своё состояние, во-вторых, записывает в эту клетку какой-то символ, может быть, другой символ, а может быть, такой же, какой был, в-третьих, перемещается по ленте на одну клетку влево или на одну клетку вправо.

Всё! Ах, да: у робота одно из состояний названо финальным: когда робот в него переходит, он уже ничего не делает. Так вот, задача считается решённой, когда робот перешёл в это финальное состояние. А ответ должен быть записан на ленте.

P – это класс задач, каждую из которых машина Тьюринга может решить за время, которое описывается полиномом (любой степени) от длины условия задачи.

Но это детерминированная машина Тьюринга.

А бывает ещё недетерминированная: это когда прочитанный символ и состояние робота определяют не один, а несколько переходов.

И тут возникает философский вопрос: какой из нескольких переходов выбрать? Есть два философских ответа.

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

Ответ второй: никакого выбора не происходит: если есть 10 переходов, то машина Тьюринга клонируется в 10 копий. И в каждой копии выбирается свой переход, так что машина выполняет эти 10 переходов параллельно по одному в каждой копии.

Понятное дело, что такая недетерминированная машина Тьюринга может размножаться на каждом такте. В результате получается ветвящееся дерево решений. Задача решена, когда хотя бы одной ветви мы получили ответ на поставленную задачу (робот на этой ветви перешёл в финальное состояние).

NP – это класс задач, каждую из которых НЕДЕТЕРМИНИРОВАННАЯ машина Тьюринга может решить за время, которое описывается полиномом (любой степени) от длины условия задачи.

Понятно, что класс P – подкласс класса NP. Но вот равны ли они?

Да, это и есть задача тысячелетия, за решение которой математический институт Клейна назначил премию в миллион долларов США: P равно NP или нет?

То есть: всякую ли задачу, которую недетерминированная машина Тьюринга может решить за полиномиальное время, детерминированная машина Тьюринга тоже может решить за полиномиальное время (пусть даже это будет полином гораздо большей степени).

Есть и другая (нестрогая) формулировка: если положительный ответ на какой-то вопрос можно довольно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно довольно быстро найти (также за полиномиальное время и используя полиномиальную память)?

При чём тут полиномиальная память?

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

Почему математики пытаются решить P-NP проблему?

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

Тут, правда, есть ещё одна проблема: если мы такой компьютер сумеем размножать по физическим мирам, то мы, конечно, получим физическую недетерминированную машину Тьюринга. Но как потом передать в наш мир ответ, полученный одним из компьютерных клонов в одном из физических миров? Это вопрос к физикам.

Кстати, кроме тезиса Чёрча-Тьюринга, который назван «физическим» и который, по сути, утверждает, что любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга, есть ещё СИЛЬНЫЙ тезис Чёрча-Тьюринга-Дойча: любой конечный физический процесс, не использующий аппарат, связанный с непрерывностью и бесконечностью, может быть вычислен физическим устройством.

Так вот я и думаю: если окажется, что P=NP, то на фига нам множественные миры? Мы можем всё тут сделать, в нашем единственном мире.

Но согласно опросу, проведённому в 2002 году среди 100 учёных, 61 человек считает, что ответ — «не равны», 9 — «равны», 22 затруднились ответить и 8 считают, что гипотеза не выводима из текущей системы аксиом и, таким образом, не может быть доказана или опровергнута.

Мне кажется, эти 8 человек знают не только теорему Гёделя о неполноте арифметики, но и что-то «знают» про физические множественные миры)))