Программируя Вселенную. Квантовый компьютер и будущее науки - Сет Ллойд

Обычные компьютеры состоят главным образом из электронных схем, которые реализуют на физическом уровне логические схемы. Логические схемы позволяют составить сложные логические выражения из простых операций, воздействующих на несколько битов за один раз. Физически логические схемы состоят из битов, соединений и логических элементов. Биты, как мы видели, могут быть в состоянии или 0, или 1; соединения позволяют перемещать биты из одного места в другое; логические элементы преобразовывают биты по одному или попарно.

Например, логический элемент «не» (not) берет входной бит и инвертирует, «переворачивает» его: «не» превращает 0 в 1, а 1 в 0. Элемент «копировать» (copy) делает копию бита: он превращает входной бит 0 в два выходных бита 00, а входной бит 1 в два выходных бита 11. Элемент «и» (and) берет два входных бита и порождает один выходной бит, который равен 1 в том и только том случае, если оба входных бита равны 1; в остальных случаях на выходе элемента «и» появляется бит 0.

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

Элемент «или» (or) берет два входных бита и порождает выходной бит, который равен 1, если хотя бы один входной бит (или оба) равен 1; если же оба входных бита равны 0, то и результат будет равен 0.

С тех пор как в 1854 г. логик Джордж Буль из Куинс-колледжа в Корке опубликовал работу «Исследование законов мышления» (An Investigation of the Laws of Thought), мы знаем, что любое логическое выражение, включая сложные математические вычисления, можно выразить с помощью операций «не», «копировать», «и» и «или». Эти операции составляют универсальный набор логических элементов.

Законы мышления Буля гласят, что любое логическое выражение или вычисление можно закодировать в виде логической схемы. Цифровой компьютер – это компьютер, который работает с использованием большой логической схемы, состоящей из миллионов логических элементов. Известные нам компьютеры, такие как Mac и PC, – это электронные воплощения цифровых машин.

Элементы «и», «или», «не» и «копировать» можно соединить так, что получится логическая схема. Логическая схема может выполнять более сложные преобразования входных битов

В электронном компьютере биты хранятся в электронных устройствах, например в конденсаторах. Конденсатор похож на ведро, в котором лежат электроны. Чтобы наполнить ведро, к конденсатору прикладывают напряжение. При нулевом напряжении конденсатор не содержит никаких лишних электронов, и его называют незаряженным. Незаряженный конденсатор в компьютере находится в состоянии «0». При напряжении, отличном от нуля, конденсатор содержит много лишних электронов и находится в состоянии «1».

Конденсаторы – не единственные электронные устройства, которые используются в компьютерах для хранения информации. На жестком диске вашего компьютера биты записываются в виде крошечных магнитов: магнит, чей северный полюс указывает вверх, означает 0, а магнит, чей северный полюс указывает вниз, показывает 1. Как всегда, любое устройство, у которого есть два надежно различаемых состояния, может хранить бит.

В обычном цифровом электронном компьютере логические элементы создаются на транзисторах. Транзистор можно воспринимать как электронный выключатель. Когда он находится в разомкнутом положении, через него не может идти электрический ток. Когда выключатель находится в замкнутом положении, ток идет. У транзистора есть два входа и один выход. В транзисторе n-типа, когда на первый вход подано низкое напряжение, выключатель разомкнут, и электрический ток не может идти из второго входа к выходу; если же напряжение на первом входе увеличить, ток начинает идти. В транзисторе p-типа все наоборот: когда на первый вход подано низкое напряжение, выключатель замкнут, и ток может идти из второго входа к выходу. Важно, что транзисторы n– и p-типов можно соединить и тем самым создать логические элементы «и», «или», «не» и «копировать».

Когда компьютер выполняет вычисления, он, в сущности, делает только одно: применяет логические элементы к битам. Компьютерные игры, редактирование текста, математические вычисления и рассылка спама – все они имеют началом процесс электронного преобразования битов, по одному или попарно.

«Невычислимость»

До сих пор мы говорили о простоте информации и вычислений. Бит – простая вещь; компьютер – простая машина. Но это не значит, что компьютеры не способны на сложное поведение. Одно парадоксальное следствие фундаментальной логичности операций компьютера состоит в том, что его будущее поведение совершенно непредсказуемо. Единственный способ узнать, что сделает компьютер, приступив к вычислениям, – подождать и посмотреть, что будет.

В 1930-х гг. австрийский логик Курт Гёдель показал, что в любой достаточно сложной математической теории есть утверждения, которые, если они окажутся ложными, сделают теорию противоречивой, и при этом их истинность доказать невозможно. Иначе говоря, любые достаточно мощные логические системы содержат недоказуемые утверждения. Вычислительный аналог недоказуемого утверждения – это невычислимая величина.

Одна известная проблема, решение которой невычислимо, – это так называемая проблема остановки. Допустим, мы запрограммировали компьютер, и он начал работать по программе. Остановится ли компьютер когда-нибудь, чтобы выдать результат, или он будет работать вечно? Нет никакой стандартной процедуры, позволяющей вычислить ответ на этот вопрос. Иначе говоря, ни одна компьютерная программа не может взять в качестве входных данных другую компьютерную программу и определить со 100 %-ной вероятностью, остановится первая программа или нет.

Конечно, для многих конкретных программ можно легко выяснить, остановится компьютер или нет. Возьмем, например, программу из одной строки «print 1 000 000 000» – компьютер, получивший на входе эту программу, напечатает число 1 000 000 000 и остановится. Общее правило, однако, таково: безостановочная работа компьютера, сколь долго она бы ни продолжалась, не дает оснований утверждать, что компьютер когда-нибудь не остановится.

Проблема остановки кажется на первый взгляд абстрактной, но у нее есть множество практических следствий. Возьмем, например, отладку компьютерных программ. Большинство из них содержат «баги», или ошибки, из-за которых компьютер ведет себя непредсказуемым образом, например «зависает». Было бы неплохо иметь «универсальный отладчик» для компьютерных программ. Такой отладчик брал бы в качестве входных данных компьютерную программу вместе с описанием того, что она должна делать, и проверял бы, выполняет ли эта программа свою задачу.

Увы, создать такой отладчик невозможно. Универсальному отладчику нужно выяснить, дает ли входная программа правильную выходную информацию. Поэтому первое, что должен проверить универсальный отладчик, – есть ли вообще у входной программы какие-либо выходные данные. Но чтобы это проверить, он должен решить проблему остановки, а это, как мы знаем, невозможно. Единственный способ выяснить, остановится ли программа, – запустить ее и посмотреть, что будет, а раз так, универсальный отладчик нам уже не понадобится. И когда в следующий раз компьютер «зависнет» из-за какого-нибудь «бага», мы сможем найти утешение в глубокой математической истине: не существует никакого систематического способа устранить все ошибки! Впрочем, можно просто чертыхнуться и перезагрузить компьютер.

Гёдель показал, что если допустить рекурсию – ссылку процедуры на саму себя, это автоматически приводит к логическим парадоксам; британский математик Алан Тьюринг показал, что рекурсии приводят к невычислимости. Заманчиво поискать подобные парадоксы в человеческом поведении. В конце концов, люди – мастера по части упоминаний о себе любимом (кажется, некоторые не способны ни к каким другим типам ссылок), и, конечно же, люди подвержены парадоксам.

Люди славятся неспособностью предсказывать свои собственные действия. Эта неспособность – важный элемент того, что мы называем свободой воли. Термин «свобода воли» относится к нашей кажущейся свободе принимать решения. Например, когда я прихожу в ресторан и беру меню, я и только я решаю, что заказать, и, прежде чем я приму это решение, даже я сам не знаю, что выберу. Наш собственный выбор в будущем неисповедим для нас самих! (Тем не менее для других он может быть не таким уж и непостижимым. Много лет мы с женой ходим в ресторан Josie’s в Санта-Фе. Тщательно изучив меню, я каждый раз заказываю половину порции фаршированных перцев с красным и зеленым чили и посоле вместо риса. При этом я сам уверен, что проявляю свободную волю: до тех пор пока я не выбрал полпорции фаршированных перцев, мне кажется, что я могу выбрать все что угодно. Но моя жена-то с самого начала знает, что именно я закажу!)