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

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

Каждая революция в сфере обработки информации связана с той или иной новой технологией – это компьютер, книга, мозг, ДНК. Эти технологии позволяют записывать и обрабатывать информацию в соответствии с некими правилами. Но что за технология связана с обработкой информации Большого взрыва? Какая машина обрабатывает информацию в вычисляющей Вселенной? Чтобы увидеть эту универсальную технологию обработки в действии, достаточно просто открыть глаза и оглянуться вокруг. Машина, выполняющая «универсальные» вычисления, – это сам Универсум, сама Вселенная.

Глава 2

Вычисление

Информация

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

Я ждал. Тишина.

Что-то здесь не так. Обычно наши студенты радуются, если им удается озадачить преподавателя, особенно если знают, что он может озадачить их самих.

Я перешел ко второму шагу: «Вопросов нет? Тогда вот вопрос вам: что такое информация?»

Молчание. Что с ними такое? В конце концов, эти студенты с первого курса заполняли свои головы информацией. Если они не начнут извергать ее обратно, мне придется перейти к третьему шагу.

«Ладно. А как вам такой вопрос: какова единица информации?»

Все хором ответили: «Бит!»

О чем говорит этот ответ, впрочем, как и молчание? Намного легче измерить количество информации, чем сказать, что она такое. А на вопрос «Сколько?» часто ответить проще, чем на вопрос «Что такое…?» Что такое энергия? Что такое деньги? Это трудные вопросы. Сколько нужно энергии, чтобы…? Сколько нужно денег, чтобы…? На такие вопросы можно дать точные и простые ответы.

«Что такое бит?», – спросил я. Теперь ответы посыпались со всех сторон: «0 или 1!»; «Орел или решка!»; «Да или нет!»; «Истина или ложь!»; «Выбор между двумя альтернативами!»

Все эти ответы правильны. Английское слово bit («бит») – сокращение от binary digit; здесь digit – это цифра, а binary («двоичный») значит «состоящий из двух частей», и бит представляет одну из этих двух альтернатив. Традиционно эти альтернативы обозначают как «0» и «1», но любые две четкие альтернативы (горячий/холодный, черный/белый, внутрь/наружу) можно считать способом хранения бита.

Бит – самая маленькая единица информации. Бросив монету, мы получим один бит: орел или решку. Два бита представляют немного больший фрагмент информации. Подбросив монету два раза, мы получим одну из четырех (два раза по две) альтернатив: орел-орел, орел-решка, решка-орел, решка-решка. Три броска монеты дадут нам одну из восьми альтернатив (два раза по два раза по две).

Как видно даже на этих простых примерах, если мы будем продолжать бросать монету, то количество альтернатив – то есть возможных исходов серии бросков – станет быстро расти. С каждым последующим броском (помните: каждый дает один бит) количество альтернатив удваивается. Поэтому, чтобы вычислить количество различных исходов в определенном сценарии, мы просто умножаем два на два столько раз, сколько у вас битов. Например, десять битов – это два умножить на два десять раз, или 1024 варианта: 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 210 = 1024, что близко к одной тысяче, или 103.

Иначе говоря, десять битов соответствуют приблизительно трем цифрам нашей обычной десятичной системы счисления, которые обозначают единицы, десятки и сотни. Измерение количества информации – просто вопрос подсчета. Вести счет в битах проще, чем в цифрах, хотя этот метод знаком нам меньше. Счет от 0 до 9 очень прост: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Но тут цифры кончаются, и следующее число – это 1, после которого следует 0, то есть 10. Число 10 – это 1 в столбце десятков и 0 в столбце единиц. Следующее число, 11, – это 1 в столбце десятков и 1 в столбце единиц. Так можно продолжать считать вплоть до 99. Следующее число – 100. Это 1 в столбце сотен, 0 в столбце десятков и 0 в столбце единиц. (Понятно теперь, почему было так сложно понять десятичную систему счета в первый раз, в пятилетнем возрасте?)

Счет в битах ведется сходным образом. Начнем: 0 = нуль, 1 = один. Пока получается неплохо, но у нас закончились двоичные цифры – биты! Следующая комбинация битов – 10, которая равняется двум: 1 в столбце двоек и 0 в столбце единиц. (Такое представление двойки – это деталь двоичной арифметики, которая дается новичкам труднее всего. Отсюда прекрасная поговорка: «Есть 10 типов людей: те, кто знает двоичную систему счисления, и те, кто ее не знает».) Следующая комбинация – 11, она соответствует трем: 1 в столбце двоек и 1 в столбце единиц. Теперь у нас закончились двухбитовые наборы.

Еще одна комбинация цифр – 100. Она обозначает число четыре: 1 в столбце четверок, 0 в столбце двоек, и 0 в столбце единиц. Затем – комбинация 101, которая обозначает пятерку (1 в столбце четверок плюс 1 в столбце единиц), 110 = шесть, 111 = семь. Число восемь представлено уже четырьмя битами: 1000, где у нас есть 1 в столбце восьмерок и 0 в столбцах четверок, двоек и единиц. У нас есть только два бита вместо десяти цифр, поэтому длина двоичных чисел увеличивается быстрее, чем обычных.

Так же как степени десяти (десятки, сотни, тысячи, миллионы) являются важными числами в обычной, десятичной системе счисления, степени двойки важны при счете битами: 1 = один = 20; 10 = два = 21; 100 = четыре = 22; 1000 = восемь = 23; 10000 = шестнадцать = 24; 100000 = тридцать два = 25; 1000000 = шестьдесят четыре = 26; 10000000 = сто двадцать восемь = 27.

Эти цифры хорошо знакомы… поварам. Английская система мер и весов – это по сути двоичная система: 8 унций в чашке, 16 в пинте (если это американская пинта; британская пинта составляет 20 унций, а тройская пинта – 12 унций), 32 унции в кварте, 64 унции в половине галлона и 128 унций в американском галлоне. Записывать числа в двоичной системе ничуть не труднее, чем измерять объем в квартах, пинтах и чашках. Например, сто сорок шесть унций составляют один галлон плюс одна пинта плюс четверть чашки: 128 + 16 + 2 = 146. В двоичной записи 146 равно 10010010, с единицей в столбце «галлонов», единицей в столбце «пинт», единицей в столбце «четвертинок» и с нулями во всех остальных. Чтобы перевести число в двоичный вид, нужно просто измерить его чайными ложками!

Американская система измерения объема основана на двоичной системе счисления

Сто сорок шесть унций составляют один галлон плюс одна пинта плюс одна четверть чашки. В двоичной записи, 146 = 10010010

Вести счет в двоичной системе легко (но не очень, если вы встретились с ней впервые). Двоичная арифметика тоже проста. Вся таблица сложения здесь выглядит так: 0 + 0 = 0; 0 + 1 = 1; 1 + 1 = 10. Таблица умножения тут выглядит еще проще: 0 × 0 = 0; 0 × 1 = 0; 1 × 1 = 1. Прелесть, правда?