?

Log in

No account? Create an account

Previous Entry | Next Entry

I. Капризы формулы

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

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

Кажется понятным, что какие-то сложные, громоздкие вычисления приведут к сложному результату, а простые формулы дадут простые, редуцируемые последовательности. Например, если положим начальное значение x1 = 1, а следующее число будем вычислять прибавлением к тому, что вычислено на предыдущем шаге единицу, что кратко записывается как xn+1 = xn+1, то мы получим ряд чисел 1, 2, 3,… Такое определение алгоритма называется итеративным, а одно повторение, одно вычисление следующего значения из предыдущего итерацией. Хорошо видно, что тысячное число в этом ряду 1000, а миллионное 1000000, и не надо для этого никаких итераций. Мы можем даже записать тот же самый алгоритм формулой x= n; так будет намного проще вычислить то же самое число за один шаг, на что наш начальный алгоритм потратил бы n шагов, тем больше, чем больше n. Таким образом, наш алгоритм xn+1 = xn+1 является редуцируемым.

Рассмотрим еще несколько простых примеров. Удобно рассматривать последовательности чисел, отображая их на графике: делая по одинаковому шагу слева направо на каждую итерацию, откладывать точку на высоте, соответствующей следующему вычисленному значению. Обратите внимание, что мы интересуемся так называемыми «ограниченными» последовательностями, о которых известно, что (при определенных ограничениях на начальное значение) все их члены останутся в определенном интервале. В наших примерах это интервал от −1 до 1. Такие ограниченные последовательности особенно интересны, потому что все повторяющиеся процессы в природе ограниченны, а неограниченный рост приводит к катастрофе: сходу лавины с горы, ядерному взрыву или взрыву сверхновой, или улетанию в бесконечный космос планеты, вращавшейся до этого по орбите вокруг двойной звезды.

Формулы на рис. 1—6 тоже итеративные. Например, формула xn+1 = xn2−1 (рис. 3) применяется так: берем начальное значение, скажем, 0,7, возводим в квадрат, получается 0,49; вычитаем 1, получаем −0,51. Это и есть следующий x. Его опять возводим в квадрат и вычитаем 1, получаем следующее значение, и так повторяем далее.

Рис. 1. Рис. 2. Рис. 3. Рис. 4. Рис. 5. Рис. 6.

Во всех случаях, мы начинаем считать от двух (достаточно произвольно выбранных) значений, 0,7 и −0,4. Уже через несколько повторов вычисления приходят к стабильным циклам, повторениям одних и тех же значений по кругу. Затухание колебаний на рис. 4 можно считать циклом с периодом 1: −0,732, −0,732, −0,732… Самый часто наблюдаемый период — это 2 (рис. 1, 2, 3, 5). Рис. 6 еще интереснее: колебания сходятся к циклу с периодом 3: −0,998, 0,744, −0,03. Меняя коэффициент при x2, можно «поймать» колебания с любым периодом от 2 до 16.

Разумеется, как только вычисление входит в такой цикл, оно становится моментально предсказуемым. Алгоритм на рис. 6 никак не «найдет» свой цикл до итерации 78. Но это еще не сложное поведение: если мы составим таблицу первых 78 значений, то всегда можем быстро найти xn по n: если n<78, то смотри таблицу, а если n78, то одно из трех значений, в зависимости от остатка от деления n на 3. Остаток может быть 0, 1 или 2, и меняется так же циклически (0, 1, 2, 0, 1…), как и вычисленные значения (−0,998, 0,744, −0,03, −0,998, 0,744…). Точно так же мы всегда сможем за не зависящее от n время определить значение, получаемое любым «зацикливающимся» алгоритмом на шаге n: все, что нам надо высчитать единожды, это две таблицы: значения до начала цикла, и каждое из значений повторяющегося цикла.

Видим, что эти все вычисления легко упрощаемы и предсказуемы. Пока что все идет, как и предполагает здравый смысл: простой алгоритм — просто предсказуемый результат. Так ведь всегда бывает?

Нет. Достаточно только положить коэффициент при x2 равным двум (рис. 7), и поведение простого алгоритма тут же делается сложным, таким, что в нем нет никаких циклических повторений. Этот алгоритм математически неупрощаем: самый простой способ узнать xn тот же, что и самый сложный: вычислить x2 из x1, x3 из x2 и так далее, и, в конце концов, xn из xn-1.

Рис. 7.

II. Бабочка крылышками бяк-бяк-бяк-бяк…

Ну и что, скажете вы, ведь математика — просто выдумка, система правил, происходящих из положенных истинными аксиом. Аксиомы те, конечно, не случайны, а выбраны для описания нашего мира; математика — не только и не столько игра для ума, сколько мощнейший инструмент для описания физического мира вокруг нас. Она бы не была таковой, если бы начала математики не были положены из наблюдений природы, от счета камушков до общей теории относительности. Однако, возразите вы, математика прекрасно описывает физические явления, но мало ли чего она еще описывает? Не все, что следует из математики, встречается в реальности! Где же видано в природе сложное поведение, чтобы оно следовало из простого итеративного алгоритма?

Ответ: на Земле и на Сатурне. Хаотические процессы были теоретически предсказаны Пуанкаре, исследовавшим систему гравитационно связанных трех тел в 1900-х годах. Однако первое практическое «столкновение» с хаосом произошло в моделях предсказания погоды Эдварда Лоренца, математика из Массачусетского технологического института, в 1960-х годах, когда он обнаружил, что модели климата чрезвычайно чувствительны к начальным условиям. Чувствительность эта столь высока, что, по образному сравнению самого Лоренца, взмах крыльев бабочки на одном континенте способен вызвать ураган на другом. А еще не только в масштабах всей атмосферы Земли, но и в стакане воды, в «смерчике», что образуется, когда утекает вода из ванны, турбулентность точно так же непредсказуема. Если бы это было не так, не нужны были бы аэродинамические трубы для испытаний обтекания воздухом автомобиля или самолета — в том числе громадные, куда устанавливают модели в натуральную величину. Конечно, обтекание рассчитывают на компьютерной модели, но обязательно проверяют, если возможно, в настоящей установке: совершенно точной модель тут быть не может. Эта ситуация отличается от других физических измерений, например, взвешивания: ведь весы измеряют не массу тела, а силу, с которой оно притягивается к Земле! Но формула, которая следует из закона всемирного тяготения, связывает массу и вес у поверхности Земли настолько точно, что многие даже не делают различий между массой и весом в ежедневных делах.

Другое интересное наблюдение было сделано «Вояджером-2», фотографировавшим спутник Сатурна Гиперион в 1980г. Мы привыкли думать, что небесная механика — образец предсказуемости, где динамика Ньютона (или Эйнштейна, если гравитация значительна) аккуратно описывает любое движение на миллионы лет вперед. Наблюдение Гипериона показало, что это не всегда так. Хотя положение спутника на орбите вокруг Сатурна предсказуемо с очень высокой точностью, его собственное вращение — хаотично, непредсказуемо вообще! Гиперион — небольшой астероид, формой напоминающий картофелину. Его асимметрия и приводит к хаотическому поведению в гравитационном поле Сатурна и множества его спутников. Теорию Ньютона он, конечно, не опровергает; просто простые уравнения этой теории дают хаотический, непредсказуемый результат. Его можно вычислить, он не случайный! Но, чтобы его вычислить, надо точно знать массы соседних спутников и расстояния до них. А насколько точно? А если не учесть величины, сравнимой со взмахом крыльев космической бабочки, получится ли другой результат? Увы, теория здесь говорит о том, что вычисление в данном случае так чувствительно к крошечным неточностям в начальных значениях, что любое долгосрочное предсказание обречено разойтись с реальностью. Вращение Гипериона капризно и непредсказуемо, как погода на Земле…

А как ведет себя наше простое уравнение при небольшом изменении начальных условий? Сходится ли результат к одному и тому же процессу, как в случаях с колебаниями на рис. 1—6, или же, напротив, достаточно «взмаха крыльев бабочки», чтобы цепочка значений, полученная этим алгоритмом, вышла совсем другой? Чтобы сравнить поведение последовательности, посмотрим на рис. 8—13. Красным пунктиром нарисован один и тот же график, а именно значения, полученные из начального x1 = 0,7. Если мы возьмем начальное значение на 0,01 больше, то есть равное 0,71, то расхождение появится уже на четвертой итерации, а дальше график пойдет совершенно иначе (рис. 8). Если прибавим одну тысячную, графики разойдутся на 9-й итерации (рис. 9). Обратите внимание, что новая последовательность, нарисованная синей линией, каждый раз после расхождения с первой ведет себя совсем иначе, по-своему! Добавление одной миллионной вызовет заметное расхождение на 18-м вычислении (рис. 10), одной миллиардной — на 28-м (рис. 11), одной триллионной — на 38-м (рис. 12), одной квадриллионной — на 47-м повторе (рис. 13). Что такое одна квадриллионная? Если песчинка весит 1 миллиграмм, то вес этой песчинки — одна квадриллионная от миллиона тонн! Миллион тонн песка — 16 000 железнодорожных вагонов — 300 грузовых поездов длиной по километру. И если из одного из всех этих вагонов вдруг выпадет одна песчинка, результат вычисления на 50-м шаге будет совершенно иным! А насколько иным  — и предположить нельзя, не посчитав.

Рис. 8. Рис. 9. Рис. 10. Рис. 11. Рис. 12. Рис. 13.

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

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

III. Vocatne fractalem quod fregimus?

На этом можно было бы и закончить, но покажу еще один тип динамических систем: фракталы. Вычисляются фракталы по итеративным формулам, очень похожим на рассмотренные нами выше, но только значения в этих формулах «двойные», состоящие из пары чисел каждое. Такие пары в математике называются «комплексными числами». Вместо графиков рисуют цветные «карты»: по оси x одно число из пары, по оси y — другое, а чтобы показать «высоту», что в наших графиках была от −1 до 1, используют разные цвета. Например, можно взять весь цветовой спектр, и задать такое соответствие: −1 будет красный, 1 фиолетовый. Тогда 0 будет обозначаться зеленым, что посередине, −1/2 оранжевым, что в середине между красным и зеленым, то есть между −1 и 0, и так далее. Можно вместо цветов взять яркость черно-белой картинки: −1 обозначить черным, 1 белым, 0 нейтральным серым. Можно придумать какое угодно соответствие, ведь делается-то это для понятности, наглядности и красоты.

И что же можно получить из простых итеративных формул? Вот такие картинки.


Зарождение звезд
в кислоте
 
 
Членение муравья
 
 
Клетки цветов
 
 
Древние

Маленькие картинки ссылаются на полноразмерные изображения, нажимайте на них, чтобы рассмотреть. А захотите посмотреть на подобные изображения еще — поищите в сети fractal gallery, и найдете их множество: «фракталопись», сочетание графического искусства с исследованиями чудесных миров, существующих лишь в вычислениях, захватывает воображение, увлекает, и потому очень популярна!

Мои изображения построены программой Fractal Explorer, бесплатной и очень давно существующей, хотя таких программ тоже много, так что, если захотите поисследовать фрактальные миры сами, то вам будет из чего выбрать инструмент.

Рекомендуемая литература

В Сети:

Книги:

  • Stewart, Ian. Does God Play Dice? Oxford: Basil Blackwell, 1989. Существует русский неопубликованный перевод: Иен Стюарт. Играет ли бог в кости?
  • Gleick, James. Chaos: Making a New Science. New York: Penguin, 1988.
  • Wolfram, Stephen. A New Kind of Science. Champaign: Wolfram Media, 2002.
  • Pickover, Clifford А. Computers, Pattern, Chaos, and Beauty. St. Martin's Press, 1990.

Tags:

Comments

( 40 comments — Leave a comment )
nature_wonder
Feb. 3rd, 2008 09:45 pm (UTC)
Мне почему-то показалось, что отсутствие упоминания (и ссылок на) Пригожина - это ваш сознательный шаг. Но не могу пока сообразить, чем он продиктован.
fregimus
Feb. 3rd, 2008 11:06 pm (UTC)
Никакого между строк в этом нет. Пригожин занимался ведь неравновесной термодинамикой и стат. механикой, разве нет? Мне просто кажется, что это намного уже и значительно глубже, чем рассмотрение хаоса «вообще». Я что-то упускаю?

Доб.: Вы могли бы посоветовать какую-то ссылку? Я добвлю.

Edited at 2008-02-03 11:12 pm (UTC)
(no subject) - nature_wonder - Feb. 4th, 2008 12:40 pm (UTC) - Expand
(no subject) - fregimus - Feb. 5th, 2008 08:58 am (UTC) - Expand
(no subject) - nature_wonder - Feb. 5th, 2008 12:00 pm (UTC) - Expand
(no subject) - fregimus - Feb. 5th, 2008 09:52 pm (UTC) - Expand
(no subject) - nature_wonder - Feb. 6th, 2008 12:31 pm (UTC) - Expand
(no subject) - fregimus - Feb. 12th, 2008 05:41 am (UTC) - Expand
(no subject) - nature_wonder - Feb. 12th, 2008 03:52 pm (UTC) - Expand
yurvor
Feb. 4th, 2008 12:03 am (UTC)
Спасибо, так вполне популярно написано - даже философы поймут, наверно :))
fregimus
Feb. 4th, 2008 03:18 am (UTC)
Спасибо за то, что прочитали! Хорошо, если бы поняли.
(no subject) - yurvor - Feb. 4th, 2008 03:40 am (UTC) - Expand
(Anonymous)
Feb. 4th, 2008 12:37 am (UTC)
Ох...спасибо, про фракталы рассказали. И картинки завидные.

А вот в начале текста у Вас там сознание упоминалось. Что лично Вы под сознанием понимаете?
faceless_lady
Feb. 4th, 2008 03:21 am (UTC)
Эт я.
(no subject) - fregimus - Feb. 4th, 2008 03:35 am (UTC) - Expand
(no subject) - fregimus - Feb. 4th, 2008 03:34 am (UTC) - Expand
(no subject) - faceless_lady - Feb. 4th, 2008 03:47 am (UTC) - Expand
(no subject) - fregimus - Feb. 4th, 2008 03:52 am (UTC) - Expand
(no subject) - faceless_lady - Feb. 4th, 2008 04:03 am (UTC) - Expand
(no subject) - fregimus - Feb. 4th, 2008 06:08 am (UTC) - Expand
(no subject) - faceless_lady - Feb. 4th, 2008 06:49 am (UTC) - Expand
(no subject) - fregimus - Feb. 5th, 2008 09:19 am (UTC) - Expand
(no subject) - faceless_lady - Feb. 5th, 2008 06:14 pm (UTC) - Expand
(no subject) - fregimus - Feb. 5th, 2008 09:30 pm (UTC) - Expand
(no subject) - faceless_lady - Feb. 5th, 2008 11:05 pm (UTC) - Expand
(no subject) - (Anonymous) - Feb. 5th, 2008 06:19 pm (UTC) - Expand
(no subject) - faceless_lady - Feb. 5th, 2008 06:19 pm (UTC) - Expand
(no subject) - faceless_lady - Feb. 4th, 2008 06:53 am (UTC) - Expand
iodiot
Feb. 4th, 2008 07:28 am (UTC)
Спасибо, с удовольствием почитал.

Вот помню когда-то экспериментировал с коэффициентами L-системы и прежде чем получить папоротник породил таких противных природе существ :)

В общем, фракталы являются удивительно ценными объектами. Неформальными словами самого же Мандельброта: "учёные мужи будут удивлены (я в этом уверен) и обрадованы, обнаружив, что отныне и впредь они получают возможность рассматривать со строгих (но справедливых) количественных позиций те формы, которые раньше им приходилось характеризовать различными "ненаучными" словами - такими, как ветвистый, водорослеобразный, извилистый, клочковатый, промежуточный, прыщавый, пушистый, рябой, сморщенный, спутанный, странный, шероховатый и т.д.".
fregimus
Feb. 5th, 2008 09:24 am (UTC)
Спасибо, с удовольствием почитал.
Пожалуйста!

породил таких противных природе существ
А Вы видели докембрийскую живность? Одни без симметрии, другие с трехлучевой симметрией… Природа тоже не с папоротников начала. :-)
termometr
Feb. 4th, 2008 09:46 am (UTC)
Вы написали этот текст как давно понятный лично Вам в популяризаторских целях или это стало Вам понятно недавно и поэтому вошло в ЖЖ-дневник?

fregimus
Feb. 5th, 2008 09:25 am (UTC)
Давно понятный.
vadim_kataev
Feb. 4th, 2008 09:10 pm (UTC)
про свободу воли, Conway's Proof Of The Free Will Theorem:
http://www.cs.auckland.ac.nz/~jas/one/freewill-theorem.html

Beauty of complex numbers, я там пару вопросов привёл, быть может ты сумеешь дать ответы:
http://vadim-kataev.livejournal.com/135060.html
fregimus
Feb. 9th, 2008 09:10 pm (UTC)
Спасибо за Конвея — с удовольствием прочитал. Читал когда-то, но в доказательсво вникать не стал, а тут — как то к случаю очень пришлось. Замечательно.

Я ведь использую сочетание «свобода воли» не в религиозном и не в философском смысле — конечно, я понимаю, что собственное ощущение свободы воли происходит от незнания того, что будет определено где-то в механизмах ума, сознанию не достижимых. Но мне все-таки легче не думать о механизмах, тем более, что о них не так много известно, а просто как-то называть результат их действия. Как садясь в машину, не думаешь о цикле Карно — а знания наши о механизмах работы мозга такие же, как, скажем, у гуманитария, хотя бы и пытливого любителя pop-sci, о работе карбюратора. В такой формулировке с моим определением даже спорить несмысленно, насколько оно того не стоит, поскольку я явно отрываю свободу воли здесь от всех филофских и метафизических связей, которыми это понятие обросло. В статье я на этом не фокусируюсь, ибо там это не важно — там можно понимать свободу воли как читателю хочется, смысла это не изменит.

На вопросы Ваши буду отвечать в Вашем журнале, и по одному, наверное — времени сейчас очень мало.
newtricker
Oct. 28th, 2008 01:27 am (UTC)
Это информационный вирус
http://newtricker.livejournal.com/62683.html

он ранее уже запускался в блогосферу, тут о нем статья
http://www.duel.ru/200131/?31_4_2
fregimus
Oct. 28th, 2008 04:58 am (UTC)
Простите, а какое это имеет отношение к моей статье? Я, честно говоря, не могу понять.
_splushka_
Mar. 1st, 2009 11:29 pm (UTC)
Беда в неточности вычислений
С этими картинками (фрактальными) есть одна беда - они, похоже, неправильные, но правильные сделать не так-то просто.
Вот возьмем для простоты всего лишь умножение чисел, дробных, с длинным хвостом после запятой. Умножив всего лишь один раз одно такое число на другое, мы получим число с вдвое более длинным "хвостом"! А если процесс итеративный и полученное на предыдущем шаге число подается на следующий шаг? Хвост станет быстро расти и.... - ВНИМАНИЕ!!! - никакой компьютер не может обрабатывать числа неограниченной длины. Он их что сделает? Правильно, УРЕЖЕТ. Т. е. произведет округление.
НО мы же знаем, что изменение чего-либо в этой цепочке (начального числа или какого-то другого звена в цепи) даже на самую малейшую йоту вызовет непредсказуемые и грандиозные последствия! Получается сущий кошмар из-за округлений, по существу - ошибок в вычислениях!
Так вот, вопрос. А не являются ли эти округления как раз ИСТОЧНИКОМ нарастания хаоса и ПРИЧИНОЙ непредсказуемости?
И к природе тоже вопрос - а умеет ли "она" вычислять с бесконечной точностью? Ведь из физики мы знаем, что нет. Что на масштабах длин 10 в степени -33 м. все начинает "кипеть" и какая-либо точность становится невозможна. Может быть, и в природе хаос объясняется конечной точностью вычислений - то есть законов природы, ну а раз законы выполняются НЕТОЧНО, то вот вам и причина ИНДЕТЕРМИНИЗМА? Причина того, что мироздание - НЕ мертвая машина Лапласа, в которой все будущее и прошлое предопределено.
Прошу прощения, мне очень сложно внятно выразить мысль, она ускользает...



fregimus
Mar. 2nd, 2009 08:36 am (UTC)
Re: Беда в неточности вычислений
К несчастью, а, скорее, даже к счастью, такой наивный взгляд является заблуждением.

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

Во-вторых, хаос проявляется и в системах, не теряющих точность — например, в целочисленных. Об одной такой системе я писал. Пример другой — Rule 30, изгугольте ее.

Хаос, таким образом, является фундаментальным свойством системы, а не возникает из-за потери точности.

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

Переносить идею вычисления на природу следует с большой осторожностью. Мы, конечно, описываем законы природы формулами, но приравнивать их к формулам так запросто, конечно же, нельзя. Любое предположение об эквивалентности некоего природного процесса вычислению следует тщательно проверять. Как, в общем, и все естественно-научные наблюдения.
Re: Беда в неточности вычислений - (Anonymous) - Mar. 2nd, 2009 03:14 pm (UTC) - Expand
(no subject) - 3seemingmonkeys - Oct. 28th, 2011 11:45 am (UTC) - Expand
( 40 comments — Leave a comment )