Книга: Золотой билет

Правило марсианина

Правило марсианина

Как узнать, какое понятие в науке – естественное, подсказанное самой природой, а какое – искусственный продукт деятельности человеческого разума? Представьте, что на Марсе обнаружили цивилизацию, которая находится примерно на таком же уровне развития, что и наша. Если для некоторого земного понятия существует марсианский аналог, полностью идентичный или хотя бы схожий по смыслу, значит, это понятие естественное, поскольку происходит из двух независимых источников.

Понятно, что цивилизации на Марсе нет и сравнивать нам там себя на самом деле не с кем, но мы ведь можем подключить воображение! Допустим, у марсиан имеется машина Экзигия – вычислительная модель, отличная от машины Тьюринга, но обладающая абсолютно теми же возможностями. Марсианский вариант тезиса Чёрча – Тьюринга гласит: все, что можно вычислить, вычислимо и на машине Экзигия. Значит, понятие вычислимости естественно, а вот понятие машины Тьюринга – нет.

В случае с классами P и NP можно обойтись без марсиан. Советские и американские математики практически не имели возможности общаться; они параллельно проделали одну и ту же работу и независимо сформулировали проблему равенства P и NP и понятие NP-полноты. Мотивы были разными: на Западе разбирались с вычислительной эффективностью, на Востоке – с необходимостью перебора; в результате обе стороны пришли туда же, куда и Курт Гёдель, опередивший их на пятнадцать лет.

Точно так же и марсиане – если бы они, конечно, существовали – могли бы прийти к проблеме равенства P и NP или чему-то подобному и отнести ее к разряду важных и естественных.

Оглавление книги