WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 30 | 31 || 33 | 34 |   ...   | 58 |

Таким образом, факт существования сложных организмов инепре­рывного рядапостепенно совершенствующихся изобретений и научных теорий (таких, как механикаГалилея, механика Ньютона, механика Эйнштейна, квантовая механика,...) говорито том, универсальность вычислений какого рода существует в реальности. Онговорит нам, что действительные законы физики, по крайней мере, до сих пор,поддают­сяпоследовательной аппроксимации с помощью теорий, дающих луч­шие объяснения и предсказания, ичто задача открытия каждой теории при наличии предыдущей легко решалась спомощью вычислений при наличии уже известных законов и уже имеющейсятехнологии. Струк­турареальности должна быть многоуровневой (какой она и была) для более легкого доступа к самой себе.Подобным образом, если рассматри­вать саму эволюцию как вычисление, она говорит нам, чтосущество­валодостаточно много жизнеспособных организмов, закодированных ДНК, что позволиловычислить (т.е. эволюционировать) организмы с более высокой степенью адаптации,используя ресурсы, предостав­ленные их предками с низкой степенью адаптации. Таким образом, мыможем сделать вывод, что законы физики, кроме того, что удостове­ряют свою собственную постижимостьчерез принцип Тьюринга, га­рантируют, что соответствующие эволюционные процессы, такие, какжизнь и мышление, не являются трудоемкими и требуют не слишком многодополнительных ресурсов, чтобы произойти в реальности.

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

Насколько эффективно можно передать данныеаспекты реальнос­тиДругими словами, какие вычисления можно практически выпол­нить за данное время и при данныхфинансовых возможностях Это основной вопрос теории вычислительной сложности,которая, как я уже сказал, занимается изучением ресурсов, необходимых длявыполнения данных вычислительных задач. Теория сложности все еще вдостаточ­ной степенине объединена с физикой и потому не дает много коли­чественных ответов. Однако онадостигла успеха в определении полез­ного приближенного различия между легко- и труднообрабатываемыми вычислительнымизадачами. Общий подход лучше всего проиллюстри­ровать на примере. Рассмотримзадачу умножения двух достаточно больших чисел, скажем. 4 220 851 и 2594209.Многие из нас помнят тот метод умножения, которому мы научились в детстве.Нужно по очере­диперемножить каждую цифру одного числа на каждую цифру друго­го и, сложив результаты, датьокончательный ответ, в данном случае 10949769651859. Вероятно, многие незахотят признать, что эта уто­мительная процедура делает умножение «легко обрабатываемым» хоть вкаком-то обыденном смысле этого слова. (В действительности, су­ществуют более эффективные методыумножения больших чисел, но этот весьма нагляден). Однако с точки зрения теориисложности, ко­тораяимеет дело с массивными задачами, решаемыми компьютерами которые не подверженыскуке и почти никогда не ошибаются, этот ме­тод определенно попадает вкатегорию «легко обрабатываемых».

В соответствии со стандартным определениемдля «легкости обра­ботки» важно не действительное время, затрачиваемое на умножениеконкретной пары чисел, а важен факт, что при применении того же са­мого метода даже к большим числам,время увеличивается не слишком резко. Возможно это удивит вас, но этот весьмакосвенный метод опре­деления легкости обработки очень хорошо работает на практике длямногих (хотя и не всех) важных классов вычислительных задач. Напри­мер, при умножении нетрудноувидеть, что стандартный метод мож­но использовать для умножения чисел, скажем, в десять раз больших,Приложив совсем незначительные дополнительные усилия. Ради дока­зательства предположим, что каждоеэлементарное умножение одной цифры на другую занимает у определенногокомпьютера одну микросе­кунду (включая время, необходимое для сложения, переходов и другихопераций, сопровождающих каждое элементарное умножение). При ум­ножении семизначных чисел 4220851и 2594209 каждую из семи цифр первого числа нужно умножить на каждую из семицифр второго числа. Таким образом, общее время, необходимое для умножения (еслиопе­рации выполняютсяпоследовательно), будет равно семи, умноженному на семь, или 49 микросекундам.При введении чисел, примерно в де­сять раз больших, содержащих по восемь цифр, время, необходимоедля их умножения, будет равно 64 микросекундам: увеличение составляет всего31%.

Ясно, что числа из огромного диапазона— безусловносодержащего любые числа, которые когда-либо были измерены как численныезначе­ния физическихпеременных — можноперемножить за крошечную долю секунды. Таким образом, умножение действительнолегко поддается обработке для любых целей в пределах физики (или, по крайнеймере, в пределах существующей физики). Вероятно, за пределами физикимо­гут появитьсяпрактические причины умножения гораздо больших чи­сел. Например, для шифровальщиковогромный интерес представляют произведения простых чисел, состоящих примерно из125 цифр. Наша гипотетическая машина могла бы умножить два таких простых числа,получив произведение, состоящее из 250 цифр, примерно за одну сотую секунды. Заодну секунду она могла бы перемножить два тысячезначных числа, а современныекомпьютеры легко могут осуществить более точный расчет этого времени. Тольконекоторые исследователи эзоте­рических областей чистой математики заинтересованы в выполнениитаких непостижимо огромных умножений, однако, мы видим, что даже у них нетпричины считать умножение трудно обрабатываемым.

Напротив, разложение на множители, по сутипроцесс, обрат­ныйумножению, кажется гораздо сложнее. В начале вводится одно число, скажем,10949769651859, задача заключается в том, чтобы найти два множителя, меньшихчисла, произведение которых равно 10949769651859. Поскольку мы только чтоумножили эти числа, мы знаем, что в этом случае ответ будет 4220851 и 2594209(и поскольку оба эти числа простые, это единственно правильный ответ). Но необ­ладая такимвнутренним знанием, как мы нашли бы эти множители В поисках простого метода выобратитесь к детским воспоминаниям, но впустую, поскольку такого метода несуществует.

Самый очевидный метод разложения намножители — делитьвво­димое число на всевозможные множители, начиная с 2 и продолжая каждым нечетным числом, до техпор, пока введенное число не разде­лится без остатка. По крайней мере, один из множителей (принимая,что введенное число не является простым) не может быть больше квад­ратного корня введенного числа,что позволяет оценить, сколько вре­мени может занять этот метод. В рассматриваемом нами случае нашкомпьютер найдет меньший из двух множителей, 2 594 209, примерно за однусекунду. Однако, если вводимое число будет в десять раз больше, а егоквадратный корень примерно в три раза больше, то разложение его на множители поэтому методу займет в три раза больше времени. Другими словами, увеличениевводимого числа на один разряд уже ут­роитвремя обработки. Увеличение его еще на один разряд снова утроит это время и т.д. Таким образом, время обработки будет увеличивать­ся в геометрической прогрессии,т.е. экспоненциально, с увеличением количества разрядов в раскладываемом намножители числе. Разложе­ние на множители числа с 25-значными множителями по этому методузаняло бы все компьютеры на Земле на несколько веков.

Этот метод можно усовершенствовать, однаковсем современным методамразложения числа на множители присуще это свойство экспо­ненциального увеличения. Самоебольшое число, которое было «в гневе» (а это было действительно так) разложенона множители, —число, мно­жителикоторого тайно выбрали одни математики, чтобы бросить вы­зов другим математикам,— имело 129 разрядов.Разложение на множи­тели выполнили с помощью сети Интернет глобальными совместнымиусилиями, задействовав тысячи компьютеров. Дональд Кнут, специа­лист по вычислительной технике,подсчитал, что разложение на мно­жители 250-значного числа при использовании самых эффективных изизвестных методов, с помощью сети, состоящей из миллиона компью­теров, заняло бы более миллионалет. Такие вещи трудно оценить, но даже если Кнут чрезмерно пессимистичен, топопробуйте хотя бы взять числа на несколько разрядов большие, и задача во многораз усложнит­ся.Именно это мы имеем в виду, когда говорим, что разложение на множители большихчисел с трудом поддается обработке. Все это весь­ма отличается от умножения, гдекак мы видели, задачу умножения пары 250-значных чисел можно элементарно решитьс помощью домаш­негокомпьютера. Никто не может даже представить себе, как можно разложить намножители числа, состоящие из тысячи или миллиона разрядов.

По крайней мере, этого никто немог представить донедавнего Времени.

В 1982 году физик Ричард Фейнман занималсякомпьютерным мо­делированием квантово-механических объектов. Его отправной точкойбыло нечто, что уже было известно в течение некоторого времени,одна­ко важность чегоне оценили, а именно, что задача предсказания пове­дения квантово-механических систем(или, как мы можем это описать, Передача квантово-механических сред ввиртуальной реальности), в об­щем случае, с трудом поддается обработке. Одна из причин того, чтоважность этого не оценили, в том, что никто и не ожидал, чтопредска­заниеинтересных физических явлений с помощью компьютера будет особо легким.Возьмите, например, прогноз погоды или землетрясения. Несмотря на то, чтоизвестны нужные уравнения, сложность их применения для реальных ситуацийобщеизвестна. Все это недавно вынесли на всеобщее обозрение в популярных книгахи статьях по хаосу и«эф­фекту бабочки».Эти эффекты не ответственны за трудность обработки о которой говорил Фейнман,по простой причине, что они имеют место только в классической физике— т. е. не вреальности, поскольку реаль­ность квантово-механическая. Тем не менее, я хочу сделатьнесколько замечаний относительно классических «хаотических» движений,толь­ко чтобыподчеркнуть достаточно различный характер невозможности получения классическихи квантовых предсказаний.

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

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

Законы квантовой механики требуют, чтобыобъект, который первоначально находится в данном положении (во всех вселенных),«рас­пространялся» всмысле мультиверса. Например, фотон и его двойники из других вселенныхотправляются из одной и той же точки светящей­ся нити накала, но затем движутсяв миллиардах различных направлений. Когда мы позднее проводим измерение того,что произошло, мы тоже становимся отличными друг от друга, так как каждая нашакопия видит то, что произошло в ее конкретной вселенной. Еслирассматрива­емымобъектом является атмосфера Земли, то ураган мог произойти, Скажем, в 30%вселенных и не произойти в остальных 70%. Субъек­тивно мы воспринимаем это какединственный непредсказуемый или «случайный» результат, хотя если принять вовнимание существование мультиверса, все результаты действительно имели место.Это многооб­разиепараллельных вселенных — настоящая причина непредсказуемос­ти погоды. Наша неспособностьточно измерить начальные состояния тут абсолютно ни при чем. Даже знай мыначальные состояния точ­но, многообразие, а следовательно, и непредсказуемость движения,все равно имели бы место. С другой стороны, в отличие от классического случая,поведение воображаемого мультиверса с немного отличными начальными состояниямине слишком отличалось бы от поведения ре­ального мультиверса: он могпострадать от урагана в 30,000001% своих вселенных и не пострадать в оставшихся69,999999%.

Pages:     | 1 |   ...   | 30 | 31 || 33 | 34 |   ...   | 58 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.