Алексей Алексенко

Это заметка про сложное, и как бы я ни старался сделать ее простой, велик шанс, что у меня ничего не получится. Поэтому, чтобы не путать читателей, я сразу изложу фактическую канву. Однажды англичанин, испанец и немец попытались вычислить некоторую величину в одном необычном — выдуманном из головы — кристалле. У них ничего не получилось. Зато они доказали, что вычислить это вообще нельзя. Кое-кто (даже среди физиков) полагает, что все это чепуха и праздная игра ума. А кое-кто считает, что здесь скрыта какая-то важная правда о реальности. Судите сами... впрочем, по порядку.

ЧАСТЬ 1. Парадокс
Людям свойственно верить в логику, и логика их обычно не подводит. Все так привыкли, что окружающий мир подчиняется логике, что даже этого не замечают. Наоборот, все страшно удивляются, когда логика дает сбой. А она иногда дает. Следите за руками.
Работники одной библиотеки решили записать все книги в два увесистых тома-каталога. В первом каталоге были перечислены те книги, в которых есть ссылки на самих себя. Во втором каталоге — книги, в которых ссылка на самих себя отсутствует.
Когда почти вся работа была закончена, библиотекари смекнули, что сами эти два каталога — тоже книги, и их тоже надо занести в какой-нибудь из каталогов. С первым каталогом все оказалось просто. Его можно было занести в сам первый каталог: тогда первый каталог будет содержать ссылку на самого себя — и окажется внесенным в первый каталог по праву. Впрочем, никакой беды не будет, если занести его во второй каталог, а в первый не вносить: тогда в первом каталоге не будет ссылки на самого себя, и потому он по праву займет место во втором каталоге.
Но куда записать второй каталог? Вроде бы его можно занести в сам второй каталог, но тогда во втором каталоге будет ссылка на самого себя, и потому его следует немедленно убрать из второго каталога и внести в первый. Но как только из второго каталога будет вычеркнута ссылка на самого себя, у него не останется никаких причин красоваться в первом каталоге, и ссылку придется вписывать снова во второй. И так бесконечно. И что прикажете делать библиотекарям?!
Эта история — не дурацкая шутка, а упрощенное изложение очень важного математического парадокса, который называется «парадоксом Рассела» (потому что Бертран Рассел его как раз и придумал). По ссылке то же самое объясняется сложнющими математическими словами.

ЧАСТЬ 2. Теорема
Бертран Рассел задумался о каталогах не потому, что был игрив умом (хотя, конечно, был) или вздумал позлить математиков. Просто математики к тому моменту и сами начали замечать, что формальные правила рассуждения не всегда работают. В частности, не всегда работает вот этот прием с «каталогами»: когда какую-то операцию применяют к ней же самой, нередко происходит нелогичное черт знает что. И вроде бы сам прием на первый взгляд не вызывает никаких подозрений: Георг Кантор, например, этим приемом доказал, что действительных чисел куда больше, чем рациональных, и такой ход мысли назвали «диагональным методом Кантора». У Кантора-то все получилось как надо; но наш библиотечный конфуз свидетельствует, что как надо получается не всегда.
В этот момент на сцену вступает математик Курт Гедель. Если профанировать его рассуждения на потребу праздному читателю, он сделал вот что: взял некоторую формальную систему математических постулатов (аксиом) и пронумеровал (каталогизировал) все-все-все следствия, которые можно сделать из нее логическим путем. А потом воспользовался «диагональным методом» и доказал, что какого-то утверждения (истинного, заметьте, утверждения!) в этом списке точно не будет. Его можно потом приписать к списку аксиом, опять выполнить всю работу... но опять что-то окажется упущенным. И так до бесконечности*, как у наших отчаянных библиотекарей. Это называется «Теоремой Геделя о неполноте». Математики сперва подумали было, что это конец математики, но потом привыкли и как-то живут с этим вот уже скоро сто лет (с 1931 года, точнее).

ЧАСТЬ 3. Глупость умной машины
Некоторым детям родители отказываются купить компьютер, и малыши думают о компьютере день и ночь, хоть его у них и нет. Похожая история случилась с Аланом Тьюрингом: он много размышлял о компьютерах в те годы, когда никаких компьютеров еще в помине не было. Он придумал то, что сейчас называют «алгоритм» — набор правил, по которым можно решить некую задачу. Машина щелкает себе по правилам шаг за шагом, и в конце выдает решение. А иногда не выдает, если задача неразрешима. Например, если попросить машину найти самое большое число в мире, она так и будет перебирать числа одно за одним, но всегда будет находить еще большее число и никогда не выдаст вам ответ.
Таким образом, понял Тьюринг, некоторые алгоритмы ведут к результату, а некоторые не ведут. Возьмем какой-нибудь алгоритм и попытаемся понять, приведет ли он к результату? Это, вообще говоря, тоже одна из математических задач. Более того, такие задачи живые математики (у которых в голове мозги, а не тьюринговский компьютер) решают постоянно: «Существует ли такое число, что...?» — это вообще типичная формулировка математической задачи.
Смекалистый читатель, который помнит о фокусах диагонального метода, — то есть что бывает, когда процедуру применяют к самой себе, — уже смекнул, в чем дело. Так и есть: Тьюринг доказал, что, вообще говоря, нет и не может быть алгоритма, способного установить, достигает ли успеха некий произвольный алгоритм. Если точнее, с алгоритмами возникает та же засада, что и с нашими каталогами: Тьюринг сконструировал такой алгоритм, который приводит к решению только в том случае... если он не приводит к решению.
Этого, в общем, достаточно для перехода к четвертой части нашего рассказа. Но мы будем непростительно поверхностны, если не добавим тут одно замечание. Мы уже упомянули, что задачи типа «Существует ли...?» или «Докажите, что не существует...» постоянно решают не только матерые математики, но и школьники, начиная класса этак с пятого. Тем не менее, согласно Тьюрингу, задачи такого рода, оказывается, вообще не решаются по формальным правилам. Тут фантазия нужна, как говорится, и интуиция. Вот примерно так (только гораздо строже) рассуждал английский математик Роджер Пенроуз, когда доказывал, что человеческое мышление не алгоритмизируемо. То есть никогда-никогда не удастся создать компьютер, который будет думать по-человечески. Более того, если вы думаете, что нейроны в голове просто выполняют алгоритм (сколь угодно сложный, самообучающийся, нелинейный, аналоговый или какой угодно еще, потому что все они заведомо присутствуют в Тьюринговом списке), то вот нет. Они делают что-то другое. Если вы заинтригованы, вот вам книжка Пенроуза «Тени разума», в которой, собственно, подробнейше изложено все то, про что мы толкуем с самого начала этой заметки.

ЧАСТЬ 4. Проклятый кристалл
Рассел придумал историю с библиотекарями из головы: вряд ли когда-то реальные библиотекари вставали в тупик от подобных парадоксов. Гедель построил свое «недоказуемое утверждение» тоже формально (хотя математики с тех пор набрали целую коллекцию примеров). Наконец, и Тьюринг сконструировал свой неразрешимый алгоритм совершенно искусственным образом. Широкую общественность слегка утешало то, что вряд ли когда-нибудь перед человечеством встанет реальная задача, в которой наш мозг упрется в предсказанную математиками стенку. Примеры пытались придумать, но все они оказались высосанными из пальца.
И вот тут приходят наши англичанин, испанец и немец. Вот, говорят, есть кристалл (кристалл, правда, они выдумали довольно причудливый, но черт его знает, всякие бывают кристаллы). Кристалл двумерный и бесконечный — такая тонкая пластинка от горизонта до горизонта. У кристалла, чтобы вы знали, есть энергетические уровни (это понимать не надо, это просто для связки), и иногда между нижними уровнями есть зазор, а иногда нету, и тогда кристалл может, например, оказаться сверхпроводящим**. Ну и вот попробуем узнать, может наш кристалл быть сверхпроводящим или нет? Есть в нем зазор между уровнями или нету?
Вот тут-то и оказалось, что алгоритм, по которому надо рассчитывать это свойство, — это и есть самый настоящий парадоксальный тьюринговский алгоритм. То есть он не приводит к результату. Это не потому, что алгоритм плохой: нерушимая логика утверждает, что ЛЮБОЙ способ расчета непременно упрется здесь в стену. Математика и логика В ПРИНЦИПЕ не позволяют предсказать, например, будет ли в этом странном кристалле наблюдаться сверхпроводимость. То есть конкретный конечный кристалл, разумеется, бывает либо таким, либо этаким — и в этом случае алгоритм, естественно, выдает результат, тупо перебрав все атомы. Но никогда нет гарантии, что начиная с какого-то числа атомов все не изменится и свойство не исчезнет. И этот критический размер кристалла заранее определить невозможно. То есть не «очень-очень сложно», или «придется считать дольше, чем существует вселенная», а вообще нельзя.
Надеюсь, все уже поняли, что это страшно важно. Если нет, вернемся к началу: людям (а в особенности ученым) свойственно думать, что мир подчиняется правилам логики и математики. И он действительно им подчиняется. И вот в точном согласии с этими правилами в этом мире есть вещи, с точки зрения математики произвольные. То есть может быть так, а может и этак, и ни то, ни другое ниоткуда не следует. Причем эти «вещи» лежат не за семью горами, это может быть простое свойство тонкой кристаллической пластинки, которое ничего не стоит определить экспериментально. А вот предсказать силой разума — ну никак.
Подробно и вполне популярно про эту работу можно прочитать в популярной части журнала Nature. Заметим, что сами авторы вовсе не кричат о том, что открыли самое важное явление в истории мировой науки — они делают массу оговорок, что, мол, и кристалл у них выдуман довольно искусственный, какого в природе пока не видели, и рассуждения хоть вроде и правильные, но ошибки в них поискать свежим глазом имеет смысл. Может, все это и не так важно, как кажется на второй взгляд (на первый-то взгляд все на свете ерунда, это проверено). Но, возможно, это и правда важно.
А еще авторы оговариваются — нашим читателям на это точно наплевать, но упомянем для порядка, — что ровно такая же засада может поджидать нас и в другой физической проблеме, так называемой «проблеме массы». Почему массы частиц такие, а не какие-нибудь другие (это если совсем грубо)? Эта «проблема Янга-Миллса» названа одной из «задач тысячелетия», и за ее решение полагается приз в миллион долларов. Если кто-то докажет, что она неразрешима в принципе, — за это, надо полагать, миллион долларов дадут все равно, не пропадать же деньгам. И если это докажут, то то, о чем мы тут сейчас так обстоятельно написали, точно не чепуха, раз за это дадут такие деньги. Это на тот случай, если наша первая линия аргументации так и не смогла до вас достучаться.

Желаю читателям (да и себе) глубочайшего понимания всех затронутых здесь вопросов. Ну а если нет — значит, не судьба.

Примечания
* Заметим, что продолжение операции до бесконечности само по себе вам не поможет: из доказательства Геделя следует, что бесконечная система аксиом тоже неполна. Сколько ты ее не «убесконечнивай», она все равно неполна (насколько я понимаю, для подпадания под это правило ей достаточно быть счетной, и да поправят меня умные математики).
** Я тут, скорее всего, ничего не понял про сверхпроводимость; надеюсь, уважаемый