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

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

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

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

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

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

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

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

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

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