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




НазваниеСет Ллойд Программируя Вселенную. Квантовый компьютер и будущее науки
страница3/22
к русскому изданию
Дата конвертации13.02.2016
Размер2.7 Mb.
ТипДокументы
источникhttp://www.rait.airclima.ru/books/Programming_Universe.doc
1   2   3   4   5   6   7   8   9   ...   22

Глава 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. Прелесть, правда?

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

Точность



«А что будет, если у нас есть бесконечное число альтернатив? – спрашивает студент. – Например, между 0 и 1 находится бесконечное количество действительных чисел».

«Если у вас есть бесконечное число альтернатив, тогда у вас есть бесконечное количество информации», – отвечаю я.

Возьмем, например, такое двоичное число: 1001001 0110110 0100000 1110100 1101000 1100101 0100000 1100010 1100101 1100111 1101001 1101110 1101110 1101001 1101110 1101111. В стандартной таблице кодирования ASCII (American Standard Code for Information Interchange – американский стандартный код обмена информацией) каждой букве или символу на клавиатуре присвоено кодовое слово из семи битов4. И если воспринимать наше число в кодировке ASCII, мы получим такие символы: I = 1001001; n = 1101110; (пробел) = 0100000; t = 1110100; h = 1101000; e = 1100101; (пробел) = 0100000; b = 1100010; e = 1100101; g = 1100111; i = 1101001; n = 1101110; n = 1101110; i = 1101001; n = 1101110; g = 1100111. Если мы прочтем буквы, то получится «In the beginning » – первые слова библейской фразы «В начале было слово…». Добавляя бит за битом, можно выписать число, соответствующее всему тексту Евангелия от Иоанна. Если мы добавим еще больше битов, то можем получить всю Библию, а за ней Коран, а за ним Сутру белого лотоса, а за ней все книги из Библиотеки Конгресса и т. д. Бесконечное число альтернатив соответствует бесконечному числу цифр или битов, бесконечному количеству информации.

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

Самый известный в мире металлический стержень был сделан из сплава платины и иридия. Он находится в Международном бюро мер и весов в Париже и на протяжении почти столетия определял длину метра. (До этого метр считался одной десятимиллионной частью расстояния от Северного полюса до экватора, измеренного вдоль парижского меридиана.) Наша линейка показала бы, что длина этого стержня – один метр плюс-минус половина миллиметра.

Если у нас есть более точный измерительный прибор, чем мерная рейка, то мы получим больше битов информации о длине того же стержня. Например, можно рассмотреть его под оптическим микроскопом. Тогда мы сможем увидеть детали, размер которых по порядку равен длине волны видимого света – немного меньше микрона, или одной миллионной доли метра. И если мы приложим к линейке микроскоп, мы сможем измерить длину стержня с точностью до микрона. Микроскоп позволит найти длину стержня с точностью в шесть значащих цифр, что соответствует примерно двадцати битам информации. Сходную степень точности можно получить с помощью интерферометра – устройства, измеряющего длину объекта длинами световых волн. Если интерферометр использует волны длиной в один микрон, он определит длину нашего стержня как один миллион световых волн.

Существуют методы, которые могут дать еще большую степень точности. В принципе можно взять устройство под названием атомно-силовой микроскоп, которое показывает отдельные атомы на поверхности, и провести им вдоль прута, измеряя его длину по числу встреченных атомов. Расстояние между атомами – порядка одной десятимиллиардной метра (10–10 м), эту единицу называют «ангстрем». Это даст нам измерение с точностью до десятой цифры, или около тридцати трех битов информации о длине стержня.

Большей точности в измерении длины макроскопического объекта, такого как стержень, добиться трудно. В определенных случаях возможно измерить расстояние с намного более высокой степенью точности, например, как в экспериментах физика Нормана Рэмзи по поиску дипольного электрического заряда нейтрона. В них определялось расстояние, составляющее примерно одну миллиардную миллиардной миллиардной части метра!

Общее количество значений, которые может различать то или иное измерительное устройство, определяется как диапазон значений (например, один метр), в пределах которого это устройство может работать, деленный на предельную точность, с которой устройство может измерять (например, один миллиметр). Диапазон, разделенный на точность, показывает, сколько отдельных значений может зафиксировать данное устройство. Далее, количество доступной информации определяется количеством битов, необходимых для того, чтобы перечислить все доступные значения. Устройство, которое выдает 33 бита информации (точность до десятой цифры) о какой-либо непрерывной величине, можно считать очень точным.

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

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

Вспомните легендарного восточного правителя, который по глупости согласился вознаградить героя зернами пшеницы: одно зерно за первую клетку шахматной доски, два зерна за вторую, четыре за третью и так далее, вплоть до двух в шестьдесят третьей степени (263) за последнюю, 64-ю клетку. Общее количество зерен при этом составляет по порядку величины 10 миллиардов миллиардов, а если точно – 18 446 744 073 709 551 615. И если длина каждого зерна равна всего одному миллиметру, все вместе они заполнят объем почти в 20 куб. км!

Как показывает этот пример, нужно совсем немного битов, чтобы выделить одну из очень большого количества альтернатив. Чтобы присвоить каждому из зерен на шахматной доске уникальный штрихкод, потребовалось бы всего 64 бита, или 64 элемента информации. Имея 300 битов, можно присвоить уникальный штрихкод каждой из 1090 элементарных частиц во Вселенной. Астрономически огромное количество возможных генетических кодов – причина невероятного разнообразия живых существ, но информация, которая позволяет воспроизвести любой из этих кодов, может быть сохранена в одной крошечной хромосоме.

Смысл



«Но разве информация не должна иметь какой-то смысл?» – спрашивает студент.

«Конечно, когда мы думаем об информации, то обычно связываем ее с каким-то смыслом», – отвечаю я. «Но что такое “смысл”?»

Философы пытаются это выяснить уже тысячи лет, с переменным успехом. Но это очень трудно, потому что смысл информации очень сильно зависит от того, как ее нужно интерпретировать. Если вы не знаете, как интерпретировать сообщение, то не понимаете его смысла. Например, если я говорю вам «да», а вы не задавали вопрос, то вы не поймете, значит мое «да». Но если вы спросите: «Можно мне взять еще один кусок пирога?», и я скажу: «Да», то вы поймете, что я имею в виду. Если вы спросите: «Сколько будет два плюс два?», а я скажу: «Да», то вы опять не поймете, что я имею в виду (хотя, наверно, начнете думать, что у меня есть только один ответ на любой вопрос). Но если вы поинтересуетесь: «Сколько будет два плюс два?», и я скажу: «Четыре», то вы поймете этот ответ. Смысл чем-то похож на порнографию: когда мы его видим, то сразу узнаем.

Вернемся к нашей строке битов: 1001001 1101110 0100000 1110100 1101000 1100101 0100000 1100010 1100101 1100111 1101001 1101110 1101110 1101001 1101110 1100111. Если интерпретировать это сообщение согласно коду ASCII, эта строка означает «В начале…». Но само по себе, без указания на то, как его нужно интерпретировать, оно ничего не означает, кроме ряда двоичных цифр. Смысл зависит только от интерпретации, как в следующем разговоре между Алисой и Шалтаем-Болтаем:


– Я не понимаю, при чем здесь «слава»? – спросила Алиса.

Шалтай-Болтай презрительно улыбнулся.

– И не поймешь, пока я тебе не объясню, – ответил он. – Я хотел сказать: «Разъяснил, как по полкам разложил!»

– Но «слава» совсем не значит: «разъяснил, как по полкам разложил!» – возразила Алиса.

– Когда я беру слово, оно означает то, что я хочу, не больше и не меньше, – сказал Шалтай презрительно.

– Вопрос в том, подчинится ли оно вам, – сказала Алиса.

– Вопрос в том, кто из нас здесь хозяин, – сказал Шалтай-Болтай.

– Вот в чем вопрос!5


Льюиса Кэрролла, автора «Алисы в стране чудес» и «Алисы в Зазеркалье», на самом деле звали Чарльз Доджсон, и он был философом-номиналистом. Доджсону очень нравилась идея о том, что слова означают лишь то, что он хочет, чтобы они означали.

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

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

Такой механизм, например, дают нам компьютеры. Они понимают языки, которые называют машинными языками (Java, C, Fortran, BASIC). Такие языки состоят из простых команд, например print («напечатать») или add («прибавить»), которые можно соединить так, чтобы дать компьютеру детальную инструкцию по выполнению сложной задачи. Если принять идею Витгенштейна о том, что значение элемента информации заключается в действии, которое она вызывает, то смысл компьютерной программы, написанной на том или ином машинном языке, заключается в действиях, которые выполняет компьютер, интерпретируя эту программу.

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

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

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

Слова могут быть символами идей и вещей, и биты тоже. Слово и бит – это средства передачи информации, но чтобы понять смысл и придать им значение, нужен интерпретатор.

Компьютер



«Что такое компьютер?» – спросил я студентов. Молчание. Это весьма странно. Я-то уверен, что мои ученики пользуются компьютерами с годовалого возраста.

Я ждал. Наконец, кто-то произнес: «Это машина, которая управляет данными, представленными в виде нулей и единиц». Другой студент возразил: «Но ты говоришь о цифровом компьютере. А как насчет аналогового компьютера? Он ведь хранит информацию в виде непрерывных сигналов напряжения».

В итоге все согласились с более широким определением: компьютер – это машина, которая обрабатывает информацию.

«Хорошо, – сказал я. – Тогда что было первым компьютером?» Студенты оживились: «Mark I»6; «Механический компьютер Бэббиджа»; «Логарифмическая линейка»; «Абак»; «Мозг»; «ДНК».

Поднялась еще одна рука: «Цифры!»

Очевидно, если компьютер – это машина, которая обрабатывает информацию, то выполнять расчеты может почти все что угодно.

«Для начала, – сказал я, – давайте рассмотрим машины, сделанные людьми и предназначенные для обработки информации, а вопрос о людях как машинах для обработки информации оставим на потом».

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

Используемая для вычислений технология налагает естественные ограничения на расчеты, которые могут быть выполнены (например, счетные камешки сильно отличаются от «персоналки» Pentium IV). Каменный компьютер хорош для того, чтобы определять количество, складывать и вычитать, но на нем уже неудобно умножать и делить. К тому же чтобы иметь дело с большими числами, нужно очень много камней.

Несколько тысяч лет назад кому-то в голову пришла прекрасная идея объединить камень с деревом: если положить камешки в углубления на деревянной доске, их будет легче передвигать туда-сюда. Потом оказалось, что если использовать вместо камней бусинки, надетые на деревянные прутья, то их не только легко передвигать туда-сюда, но и трудно потерять.

Деревянный компьютер, такой как абак или русские счеты, – мощный вычислительный инструмент. До изобретения электронно-вычислительных машин опытный счетовод мог выполнять вычисления на счетах лучше обученного оператора суммирующей машины! Но абак – не просто удобная машина для того, чтобы перекладывать камешки. Она воплощает в себе важную математическую абстракцию – нуль. Понятие нуля оказалось наиболее важным элементом системы арабских цифр – системы, позволяющей обозначать сколь угодно большие величины и легко с ними управляться. Абак или счеты – механическое воплощение этой системы. Но что появилось раньше, привычные нам цифры или абак? Учитывая происхождение слова zero («нуль») и возраст первого абака, вполне возможно, что устройство возникло раньше, чем оформилась концепция нуля7. Иногда машины создают идеи.

А идеи создают машины. Сначала камень, потом дерево: какой материал мог бы стать следующим шагом в обработке информации? Кость. В начале XVII в. шотландский математик Джон Непер открыл способ заменить умножение сложением. Он вырезал из слоновой кости палочки, нанес на них логарифмические отметки, соответствующие тем или иным числам, и стал выполнять умножение, сдвигая палочки друг относительно друга так, чтобы установить правильным образом отметки, соответствующие двум сомножителям. Суммарная длина двух палочек давала произведение двух чисел. Это была первая логарифмическая линейка.

В начале XIX в. один эксцентричный англичанин по имени Чарльз Бэббидж предложил делать компьютеры из металла. Разностная машина Бэббиджа, предназначенная для вычисления элементов тригонометрических и логарифмических таблиц, должна была иметь в своей основе валы и шестерни, подобно паровому двигателю. Положение каждой шестерни задавало ту или иную информацию, а потом машина обрабатывала эту информацию, вводя шестерни в зацепление друг с другом и вращая их. Хотя машина Бэббиджа была полностью механической по своей конструкции, придуманный изобретателем способ организации информации предвосхищал методы, принятые в современных электронно-вычислительных машинах. В ней были центральный процессор и банк памяти, который мог хранить как программу, так и данные.

Несмотря на щедрую финансовую поддержку от британского правительства, Бэббиджу так и не удалось построить разностную машину. В начале XIX в. еще не было ни технологии прецизионной обработки металла, ни достаточно твердых сплавов для валов и шестерней. (Усилия его, однако, не пропали зря: инженеры Бэббиджа как раз и разрабатывали методы точной механической обработки металла и более прочные сплавы, и это значительно ускорило темпы промышленной революции.) К концу XIX в. уже существовали эффективные механические калькуляторы, но большим компьютерам пришлось дожидаться начала XX в., когда были изобретены электронные схемы.

К 1940 г. началась международная конкуренция между различными группами ученых, пытавшимися создать компьютер на основании электронных переключателей, например электронных ламп или электромеханических реле. Первую простую электронно-вычислительную машину в 1941 г. создал немецкий ученый Конрад Цузе. За ним последовали большие компьютеры, построенные в 1940-е гг. в Соединенных Штатах и Великобритании. Эти компьютеры представляли собой несколько комнат, заполненных электронными лампами, переключателями и источниками питания, но их вычислительная мощь была невелика – в миллион раз меньше, чем производительность компьютера, на котором я пишу эту книгу.

Эти первые электронные компьютеры стоили очень дорого, но оказались весьма полезными, что оправдывало усилия по их совершенствованию. В 1960-х гг. электронные лампы и электромеханические реле заменили транзисторами – полупроводниковыми переключателями, которые были надежнее, меньше по размеру и потребляли меньше энергии. Полупроводник – это материал (например, кремний), который проводит электричество лучше, чем изоляторы (например, стекло или резина), но хуже, чем проводники (например, медь). В конце 1960-х транзисторы удалось сделать еще меньше – их вытравливали в составе интегральных схем на кремниевой подложке, и эти схемы уже содержали все компоненты, необходимые для обработки информации, на одном полупроводниковом чипе.

Начиная с 1960-х гг. развитие фотолитографии – технологии изготовления все более сложных схем – приводило к уменьшению размеров компонентов интегральных схем примерно вдвое каждые восемнадцать месяцев. В результате производительность компьютеров удваивалась с той же скоростью. Это явление называется законом Мура. В настоящее время толщина соединений в интегральных схемах обычного компьютера составляет всего 1000 атомов.

Я бы хотел дать определения некоторых типов компьютеров, о которых мы будем говорить ниже. Цифровой компьютер – это вычислительная машина, которая применяет логические схемы к битам; цифровая машина может быть электронной или механической. Классический компьютер – это компьютер, выполняющий вычисления на основе законов классической механики. Классическая цифровая машина выполняет вычисления, проводя классические логические операции с классическими битами. Электронный компьютер выполняет вычисления с помощью электронных устройств, таких как электронные лампы или транзисторы. Цифровой электронный компьютер – это цифровой компьютер электронного типа.

Аналоговый компьютер оперирует не с битами, а с непрерывными сигналами; он так называется, потому что его, как правило, используют для создания вычислительных «аналогов» физической системы. Аналоговый компьютер также может быть электронным или механическим.

Наконец, квантовый компьютер действует на основании законов квантовой механики. У квантового компьютера есть и цифровые, и аналоговые аспекты.

Логические схемы



Чем занимаются наши все более мощные компьютеры? Они обрабатывают информацию, разбивая ее на биты и оперируя с ними, по нескольку битов за один раз. Как мы уже говорили, информация, которая должна быть обработана, представлена компьютеру в форме программы, ряда инструкций на машинном языке. Программа закодирована в память компьютера в виде последовательности битов. Например, команда print («печатать») в коде ASCII выглядит так: P = 1010000; R = 1010010; I = 1001001; N = 1001110; T = 1010100. Компьютер считывает программу по нескольку битов за шаг, интерпретирует эти биты как инструкцию и выполняет ее. Потом он видит следующие несколько битов и выполняет следующую инструкцию. И так далее. Сложные процедуры можно построить из наборов простых инструкций, но об этом мы поговорим позже.

Обычные компьютеры состоят главным образом из электронных схем, которые реализуют на физическом уровне логические схемы. Логические схемы позволяют составить сложные логические выражения из простых операций, воздействующих на несколько битов за один раз. Физически логические схемы состоят из битов, соединений и логических элементов. Биты, как мы видели, могут быть в состоянии или 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 в Санта-Фе. Тщательно изучив меню, я каждый раз заказываю половину порции фаршированных перцев с красным и зеленым чили и посоле вместо риса. При этом я сам уверен, что проявляю свободную волю: до тех пор пока я не выбрал полпорции фаршированных перцев, мне кажется, что я могу выбрать все что угодно. Но моя жена-то с самого начала знает, что именно я закажу!)

Непостижимая природа наших решений при использовании свободы воли – это аналог проблемы остановки: мы приводим в движение свои мысли, но не знаем, куда они приведут и приведут ли куда-нибудь вообще. И даже если они куда-то приведут, мы не знаем, куда, – до тех пор, пока там не окажемся.

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

Эта прекрасная загадочность чистого разума возвращает нас к вопросу о роли логики во Вселенной. Размышляя у себя дома в Кордове над трудами Аристотеля, мусульманский философ XII в. Аверроэс (ибн-Рушд) пришел к выводу, что бессмертна в человеке не душа, но способность мыслить. Разум бессмертен именно потому, что не принадлежит никому в отдельности; это общее свойство всех мыслящих существ.

Компьютеры, конечно, обладают способностью мыслить и способностью к рекурсии. Именно поэтому их действия с необходимостью являются непостижимыми. Следовательно, по мере того как они становятся более мощными и выполняют все более разнообразный набор задач, их непредсказуемость приближается к непредсказуемости человека. По логике Аверроэса, они начинают обладать той же степенью бессмертия, что и люди.

Запрограммировать компьютер так, чтобы он выполнял простые человеческие задачи, очень сложно: заставить робота пропылесосить комнату или освободить посудомоечную машину, даже при минимальных требованиях к качеству, – проблема, над которой бьются уже несколько поколений исследователей в области искусственного интеллекта. И наоборот, не нужно больших усилий, чтобы запрограммировать компьютер так, чтобы он вел себя непредсказуемо и сводил нас с ума. С точки зрения способности все запутать и испортить компьютер с каждым днем становится все больше похож на человека8.


1   2   3   4   5   6   7   8   9   ...   22

Похожие:

Сет Ллойд Программируя Вселенную. Квантовый компьютер и будущее науки iconКвантовый Компьютер и его роль в физике сложных систем
На таком устройстве можно реализовать любую последовательность одно-трех кубитных (кубит квантовый бит) элементарных унитарных операций...
Сет Ллойд Программируя Вселенную. Квантовый компьютер и будущее науки iconКонференцию ман рк «Интеграция образования и науки шаг в будущее», посвященную хх-летию Республики Казахстан
Павлодарское отделение Малой Академии наук Республики Казахстан (ман рк) совместно с Инновационным Евразийским университетом проводит...
Сет Ллойд Программируя Вселенную. Квантовый компьютер и будущее науки iconИнформатика дегеніміз не?
Сабақтың тақырыбы: Информатика дегеніміз не? Компьютер – ақпарат өңдеу құралы. Компьютер өңдейтін ақпарат түрі. Компьютер – аппараттық...
Сет Ллойд Программируя Вселенную. Квантовый компьютер и будущее науки iconЕстественные науки 1 физико-математические науки 2 химические науки 6
Науки о земле (геодезические. Геофизические. Геологические и географические науки) 7
Сет Ллойд Программируя Вселенную. Квантовый компьютер и будущее науки iconОлимпиада «Будущие исследователи – будущее науки». Отборочный тур. Русский язык, 7-8 классы
...
Сет Ллойд Программируя Вселенную. Квантовый компьютер и будущее науки iconРеспублики казахстан комитет по надзору и аттестации в сфере образования и науки
А. Эйнштейн, Н. Бор, М. Борн, В. Гейзенберг, В. И. Вернадский, К. И. Сатпаев и др Концепции науки: основные подходы в философии и...
Сет Ллойд Программируя Вселенную. Квантовый компьютер и будущее науки iconКомпьютер сочиняет
Компьютер может использовать заданный объем информации и вложенный в неё запас образных выражений. Сочетание информации, образов,...
Сет Ллойд Программируя Вселенную. Квантовый компьютер и будущее науки iconВеселовский Сергей Дни студенческой науки 2004. Секция по терроризму. Доклад. Будущее антитеррористической коалиции
Ирак стал единственным арабским государством, которое отказалось осудить теракты 11 сентября 2001 года, однако при этом оно и не...
Сет Ллойд Программируя Вселенную. Квантовый компьютер и будущее науки iconПояснительная записка Обыденным делом стал компьютер в нашей жизни. Ведь на самом деле, при разумном использовании компьютер оказывается таким замечательным другом и помощником Хочется в это верить и с этими мыслями садиться за компьютер
Программа предназначена для развития творческой активности детей, обеспечивающая развитие познавательных интересов в обучении и составляющим...
Сет Ллойд Программируя Вселенную. Квантовый компьютер и будущее науки iconГлаза и компьютер
Раньше считалось, что зрение портится, если много смотреть телевизор и читать в темноте и движущемся транспорте. Теперь добавился...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©kzdocs.docdat.com 2012
обратиться к администрации
Документы
Главная страница