Параллельно с фокусировкой внимания на алгоритмах появилось обобщение понятия функции. В самом общем смысле функция ƒ — произвольное соотношение между математическими объектами. Считается, что функция вычислима, если существует алгоритм, который создает на выходе ƒ(х) для любого значения х, для которого ƒ(х) определено, то есть для так называемой области определения ƒ(х). Лишь в конце девятнадцатого столетия, когда были построены патологические функции, до математиков дошло, что функция может и не быть вычислимой. В результате внимание переместилось на вычислительные алгоритмы. Стало совершенно ясно, вычисляет ли данный алгоритм именно ту функцию, которая необходима. Но если невозможно было подобрать ни одного алгоритма, необходимо было доказать, что такового алгоритма вообще не существует. Появилась необходимость в точном определении понятия алгоритма. В статье Геделя содержались идеи относительно рекурсивных функций, где необходимая функция получалась путем последовательности промежуточных функций. Эти концепции оказались очень плодотворными для определения вычислительных алгоритмов. В 1936 году Алонзо Чёрч в Принстоне и Алан Тьюринг в Кембридже независимо друг от друга опубликовали свои концепции исчисляемости. Затем Тьюринг показал, что эти два понятия полностью эквивалентны. Определение алгоритма Тьюринга было основано на модели вычислительной машины, названной Чёрчем «машина Тьюринга». На вопрос о том, существует ли алгоритм, который мог бы определить, верна формула или нет, был дан отрицательный ответ. Эти результаты, совместно с данными Геделя, окончательно похоронили надежду на то, что компьютер однажды сможет определить истинность и ложность всех математических суждений. Однако сосредоточенность на алгоритмах положила начало развитию программного обеспечения, которое объявило о начале новой эры в математической физике. Вычислительная математика вернулась к обсуждению старых проблем динамики, вроде стабильности Солнечной системы, а также обратила взор на биологические системы и саму сложную динамику жизни.
В естественных науках автоматы играли роль, значение которой непрерывно возрастало и которая к настоящему времени стала весьма значительной. Этот процесс развивался в течение нескольких десятилетий. В конце этого периода автоматы стали захватывать и некоторые области математики, в частности (но не только) математическую физику и прикладную математику. Их роль в математике представляет интересный аналог некоторых сторон жизнедеятельности организмов в природе. Как правило, живые организмы гораздо более сложны и тоньше устроены и, следовательно, значительно менее понятны в деталях, чем искусственные автоматы. Тем не менее рассмотрение некоторых закономерностей устройства живых организмов может быть весьма полезно при изучении и проектировании автоматов. И наоборот, многое из опыта нашей работы с искусственными автоматами может быть до некоторой степени перенесено на наше понимание естественных организмов.
При сравнении живых организмов и, в частности, наиболее сложно организованной системы — нервной системы человека — с искусственными автоматами следует иметь в виду следующее ограничение. Естественные системы чрезвычайно сложны, и ясно, что проблему их изучения необходимо подразделить на несколько частей. Один метод такого расчленения, особенно важный в нашем случае, заключается в следующем. Организмы можно рассматривать как составленные из частей, из элементарных единиц, которые в определенных пределах автономны. Поэтому можно считать первой частью проблемы исследование структуры и функционирования таких элементарных единиц в отдельности. Вторая часть проблемы состоит в том, чтобы понять, как эти элементы организованы в единое целое и каким образом функционирование целого выражается в терминах этих элементов.
Джон фон Нейман. Статья «Общая и логическая теория автоматов»
24. Хаос и сложность
С начала девятнадцатого века математика рассматривалась как аналитический и логический предмет; к концу столетия она произвела на свет целый зверинец математических монстров, вроде непрерывных функций, не имеющих касательных. В динамике задача трех тел — тестовый пример стабильности Солнечной системы — все еще не имела никаких устойчивых решений, и Анри Пуанкаре, анализируя частный случай этой задачи, создал очень сложную, запутанную структуру. Изменение точки зрения с аналитической на геометрическую показало математикам, что то, что казалось ужасающим беспорядком, имело много подобий с тем видимым беспорядком, коим является реальным мир. Математические монстры, оказалось, охраняли пещеру Аладдина с новыми и замечательными математическими объектами. Вход в этот мир осуществлялся с помощью компьютеров, которые стали лабораториями новой математики, базирующейся на алгоритмах. В свою очередь, сделанные при этом открытия могли поддержать аналитическое представление и приводили к пониманию, что «простые» системы, которые использовались математиками, — всего лишь верхушка колоссального айсберга.
Имя, неразрывно связанное с фрактальной геометрией, — Бенуа Мандельброт. Ныне он профессор Йельского университета и почетный профессор IBM
[26]. Его интерес к тому, что он позже назвал фракталами, возник в 1951 году. В 1977 году Мандельброт издал книгу «Фракталы: форма, случай и размерность», а в 1982 году вышло ее пересмотренное и расширенное издание — «Фрактальная геометрия природы». О фракталах было написано очень много, широко известны создаваемые ими узоры в стиле рококо. В динамике была хорошо известна идея «аттракторов», например, орбита планеты — это эллиптический аттрактор. В ней существуют некоторые возмущения, но они удерживаются в определенных пределах. При решении полиномиалов числовыми методами, если итерации сходятся к определенному решению, то это решение — аттрактор. Иногда корень, который, как известно, может быть выражен графически, не может быть получен методом итерации — такой корень называют «отражателем». Но в хаотической системе вроде турбулентного воздушного потока аттрактор представляет собой фрактал, и он известен как странный аттрактор.
Как только мы понимаем, как надо правильно на это смотреть, мы находим хаотическое поведение в самых простых ситуациях. Логистическое разностное уравнение z = λz (1 — z) — простое квадратное уравнение со всего одним изменяющимся коэффициентом, обозначенным λ. Уравнение имеет два корня, как и предполагается для квадратного уравнения, но если мы используем итерационную процедуру, то обнаружим некоторые удивительные свойства. Для большинства значений λ итерация «взрывается» и отклоняется к бесконечности. Но если мы начнем с λ = 1 и начнем медленно увеличивать значение этого коэффициента, мы увидим, что итерация не отклоняется и при этом не сходится к единственному значению: вместо этого она колеблется между рядом значений. В некоторый момент система ведет себя хаотически, выполняя дикие скачки между множеством чисел. Если мы теперь добавим комплексные числа, сегмент вещественной оси разветвляется, демонстрируя фрактальную структуру. С помощью простого преобразования разностное уравнение принимает вид другого квадратного уравнения z = z2 - т. Итерационный процесс весьма прост, но очень утомителен, если его выполнять вручную. Мандельброт первым с помощью компьютера распечатал то, что теперь называют множеством Мандельброта для случая, где z — комплексное число. Множество Мандельброта — по сути, ряд чисел, и его исходная одноцветная распечатка представляла собой черно-белый текст, состоящий из значений m, для которых итерация не сходилась к бесконечности — то есть тех, для которых итерации оставались ограниченными. Лишь после того, как компьютеры обзавелись более мощными принтерами и увеличилась сложность компьютерной графики, стала видна невероятная красота этой структуры, с ее зубчатыми завитками. Эта простая система выявила многие характеристики, которые Мандельброт стремился свести воедино. С помощью компьютера стало возможно увидеть самоподобие, столь характерное для фракталов, когда путем изменения масштаба изображения выполняется погружение внутрь множества, где обнаруживаются мини-множества, подобные большему целому. Возвращаясь к разностному уравнению, для комплексных значений λ итерации создают то, что Мандельброт любил называть «драконами». Страшные монстры математического анализа переродились в прекрасных существ, которые с радостью были приняты в дружную семью математики.
