Владимир Бронников
В том, что ХХ век назовут веком великих физических открытий, никто не сомневался вплоть до конца текущего столетия. Однако темпы развития компьютерной индустрии за последние 10 лет поставили под сомнение этот тезис. Что же произошло? Почему наша жизнь все больше стала походить на непрерывное поглощение не только пищи материальной и духовной, но и пищи информационной? Я не претендую на ответ, а только попытаюсь показать небольшую часть того научного потенциала, который, с одной стороны, лежит в основе этого необычного прогресса, а с другой стороны, дает возможность любому владельцу PC поучаствовать в захватывающем процессе и ощутить себя одним из тех, кто находится на переднем крае сегодняшней науки.
Что есть компьютер, как не инструмент, усиливающий наш интеллект? Кто-то предпочитает использовать его для развития маленького отдела своего мозга, бесконечно проходя лабиринты Doom, кто-то - для поиска информации по своей специальности в сети Internet и расширения своих профессиональных навыков, но есть и те, кто, устав решать однотипные задачки на поиск числа в массиве или уравнения численными методами, хочет попробовать свои силы в программировании. Будь вы школьником, только-только освоившим простые инструменты Windows 95, или профессиональным писателем на SQL, вам не избежать тяги к самостоятельному созданию новых алгоритмов, ибо они позволяют независимо от инструмента, на котором вы работаете (или собираетесь работать), понять саму суть процесса алгоритмизации. Ведь текст программы - это только код, реализующий задуманный алгоритм, и не более того. А кто же придумывает алгоритмы или, что еще важнее, новые понятия и миры, в которых “живут” эти алгоритмы?
С чего начинался компьютер
Несмотря на давнюю историю вопроса, хотелось бы отметить основные вехи рождения компьютера в современном его понимании.
Итак, одновременно с тем, как умные физики изобрели электронные приборы типа транзистора, в математике и теории управления созрели ключевые идеи современного компьютеростроения. Эти идеи вылились в понятие “алгоритм”. Последовательность действий, подчиненная определенным правилам и формализованная впервые Аланом Тьюрингом в так называемой машине Тьюринга, представляла собой набор абстрактных устройств: лента, на которую можно было “записать” числа, головка, способная перемещаться вдоль ленты и читать или писать эти числа с ленты, и устройство, которое в соответствии с заданными правилами могло управлять головкой. Исследования такой абстрактной машины привели к фундаментальным открытиям: появлению современных типов данных, разным процедурным языкам программирования и объектно-ориентированным технологиям.
Второе фундаментальное достижение в области первичного (физического) представления всех данных в двоичной форме - нолики и единички. Двоичная система счисления надолго осталась с нами, и все сегодняшние компьютеры работают именно на этом фундаментальном принципе (за исключением многочисленных экспериментальных образцов).
Но были и такие прорывы в будущее, которые до сих пор остаются красивыми идеями, например идея “самовоспроизводящихся” клеточных автоматов, сформулированная Дж. Фон Нейманом, одним из столпов современной кибернетики.
Немногие математические идеи того времени (30 - 40-е годы) реализованы сегодня, и одна из них - теория клеточных автоматов. А самым замечательным приложением этой теории стала известная многим игра “Жизнь”. Она появилась в 1970 г. и получила название ”Игра Конвея”, по имени ее изобретателя Дж. Конвея.
Все сегодняшние достижения компьютерной технологии сводятся в основном к стремлению производителей сделать из компьютера потребительский товар, который решал бы ряд функциональных задач и не требовал от пользователя большой сообразительности и уж тем более не стимулировал тягу к пониманию происходящих в этом аппарате процессов.
Этим занимаются программисты. Они знают, какие средства использовать для решения тех или иных задач, и их работа зачастую сводится к настройке готовой системы и поддержке ее функционирования на уровне пользовательского интерфейса.
С чего начиналась “Жизнь”
В отличие от искусственных приборов, которые мы называем компьютерами, естественные объекты (люди, животные, горы и моря) образовались не в головах ученых, а возникли в процессе длительной эволюции ВСЕЛЕННОЙ и того относительно короткого промежутка времени, когда появились первые живые существа и Homo Sapiens. Ясно, что жизнь во всех ее проявлениях - от геосферы до уникальных способностей человеческого мозга - это явление на порядки более сложное, чем набор микросхем, подчиняющийся программе. И процессы, происходящие при решении задач в мозгу человека, построены совершенно на других физических и алгоритмических принципах, чем те, что происходят в современных компьютерах. И главное отличие (над ним тоже не одно десятилетие бьется теория искусственного интеллекта) заключается в том, что машина не может мыслить, если под мыслительным процессом понимается прежде всего вся совокупность физико-химических процессов, происходящих в мозгу человека как представителя биологического вида.
Многочисленные проекты (и соответственно большие деньги) были нацелены на то, чтобы создать системы, подобные мозгу, - перцептроны, нейрокомпьютеры, оптические машины, неокогнитроны - и другие частные разработки (например, решение шахматной задачи). Кроме претензий на создание “мозгоподобных” машин эти проекты нашли свое применение в военных, коммерческих и других целях. Однако фундаментальные законы мышления остаются тайной за семью печатями и не следует рассчитывать на их быстрое понимание.
Какие же математические (и соответственно алгоритмические) модели могут лежать в основе будущих компьютеров и какие потребуются усилия от разработчиков и ученых, чтобы эти компьютеры появились? Будут ли это новые архитектуры, содержащие тысячи и миллионы отдельных вычислительных устройств (или процессоров), способные воспринимать естественную речь и самостоятельно ориентироваться в окружающей среде? Или это будут так называемые биокомпьютеры, построенные на основе белковых молекул и производящие “вычисления” аналоговым способом? Никто точно не знает.
Искусственная жизнь
Вернемся к вопросу о том, с чего начинался компьютер. Магистральное направление развития всей современной вычислительной науки и соответственно компьютеростроения пошло по пути создания процессоров, которые работают на принципе выполнения преобразований двоичных последовательностей - слов, алгоритмы переводят биты в байты, байты в цифры или знаки, цифры в арифметические операции и операции над данными, данные отображаются в привычной форме на экране монитора. Но есть и другая математика. Она не оперирует двоичной арифметикой, и для нее мощность вашего PC - сущие пустяки, поскольку алгоритмы этой математики построены на принципиально других законах, и, какой бы ни была мощность процессора Intel и сколько бы процессоров ни работало над задачей, можно сформулировать очень простую задачу, с которой они справятся только за очень длительное время.
Имя этой математике - клеточные автоматы (КА). Что же такое клеточные автоматы? Представим себе, что задано некоторое пространство, и для простоты рассмотрим лист бумаги, расчерченный на регулярные области (в частном случае это будут отдельные клетки - т. е. лист в клеточку). Заметим, что мы уже сделали два теоретических упрощения: пространство выбрали двухмерным (для наглядности), а на плоскости задали топологический закон (отдельная клетка имеет строго фиксированное число соседей). Но даже при таком ограничении математические объекты, о которых мы говорим, обладают на удивление сложным поведением.
Ключевыми понятиями для определения поведения системы КА служат следующие параметры:
- число состояний клетки на поле (минимум 1, максимум зависит от решаемой задачи) - А;
- минимальная окрестность клетки: симметричная - 4 соседа (на севере, юге, востоке и западе - окрестность Неймана), полная - 8 соседей, т. е. еще 4 клетки по диагоналям (окрестность Мура);
- правило “жизни” клетки, определяемое как ее состояние в момент времени К+1 в зависимости от ее состояния и состояния клеток минимальной окрестности в момент времени К. Нетрудно посчитать, что таких правил может быть (А в степени А) в степени 8.
Есть еще ограничения для такой модели - это свойства границы поля. Поскольку в реальных моделях такая граница существует, то обычно законы поведения автоматов (а вы уже догадались, что отдельные клетки поля это суть маленькие автоматики-роботы) на границе поля задаются отдельными правилами. Другое ограничение на КА - это понятие синхронного времени: все состояния клеток-автоматов изменяются одновременно! И это фундаментальное свойство в корне отличает модель вычислений в КА от всех алгоритмов последовательного вычисления, положенных в основу современных компьютеров.
Алгоритмы для КА строятся, исходя из предположения о том, что моделируемое явление или процесс можно представить как пространственную систему, состоящую из “физического” пространства, в котором располагаются отдельные “существа” и каждое из них “живет” по одним и тем же правилам - законам (выше мы их назвали “правила КА”). Самый простой и необычный автомат был предложен Дж. Конвеем, и он описывается следующими правилами.
1. Каждая клетка имеет одно из двух состояний - “живое” и “мертвое” (1 и 0).
2. Правила, которые определяют состояние клетки в момент времени К+1, просты:
- если живая клетка на такте К имеет меньше 2 или больше 3 соседей (в минимальной окрестности из 8 клеток), то на такте К+1 она умирает (здесь простая аналогия с реальной жизнью - недостаток питания или перенаселенность);
- в пустой клетке на такте К+1 появляется живая клетка, если у исходной клетки в минимальной окрестности ровно 3 соседа (3 родителя!).
Теперь для исследования законов такого искусственного мира достаточно задать начальное состояние системы - какие из клеток поля в начальный момент времени находятся в живом состоянии. Для того чтобы каждый из вас мог самостоятельно написать алгоритм для своего PC, достаточно указать, что для такого преобразования поля клеток необходимо в памяти вашего компьютера зарезервировать два двухмерных массива для состояния системы в момент времени К и соответственно в момент времени К+1.
А теперь маленький тест для читателей
Если вы запрограммировали эту задачку за 1 час, то вы - профессионал и вам положена приличная зарплата в вашей компании. Если вы потратили несколько часов на решение задачи, то вы сносно программируете, но слабы в алгоритмах. И наконец, если вы потратили на решение задачи больше суток, то бросьте это занятие и попросите написать программу любого студента 3 - 4-го курса политехнического вуза, и если вы сможете ему объяснить задачу, то считайте, что вы аналитик, а не писатель программ.
Что позволяют моделировать КА
За последние 20 лет теория КА испытывала взлеты и падения, связанные с тем, что первоначальная идея об универсальном аппарате для моделирования природных явлений не сработала, как только ученые приступили к моделированию реальных процессов в физике, химии и биологии. Однако эти исследования не пропали даром, поскольку поставили вопросы, на которые сегодня отвечают новые поколения ученых. Среди них следующие.
Как по физическому описанию задачи построить правила для конкретного КА? Как исследовать КА с размерностью больше двух и неограниченным размером поля? Как ввести в модели КА неоднородность среды?
Вопросов может быть значительно больше, но принципиальным остается один: а есть ли альтернатива такому подходу? Ведь существует огромное количество различных математических систем, пригодных для формального (формульного) описания физических и иных задач. Однако пока нет таких математических методов, которые бы, с одной стороны, были интуитивно понятны при описании физического явления и, с другой стороны, позволяли построить простые алгоритмы моделирования таких физических задач для реализации на современных компьютерах. Еще более важным шагом стало бы создание компьютера с архитектурой КА, что позволило бы решать задачи на принципах полного параллелизма. Как показывают эксперименты с прототипом такой машины, производительность в данном случае увеличивается в миллионы и миллиарды раз (Т. Тоффли).
Примеров применения КА много, приведем наиболее удачные.
1. Моделирование процессов фильтрации в физике твердого тела.
2. Моделирование социальных систем (голосования, распространения инфекции и т. п.).
3. Моделирование алгоритмических процессов с использованием универсальной математики для параллельных вычислений; КА как новая универсальная модель параллельных вычислений, по своей концептуальной силе аналогичная машине Тьюринга - модели последовательных вычислений.
4. Моделирование самоорганизующихся систем типа реакций Белоусова - Жаботинского.
5. Моделирование простых экосистем и популяций. Например, известная задача о замкнутой экосистеме “Акватор”, моделирование динамики популяций двух видов рыб - акулы и нехищные рыбы (попробуйте построить алгоритм для КА в такой модели).
Но для наших читателей, наверное, наиболее интересными могут оказаться системы КА, которые позволяют создавать так называемые “обои” или, по другой терминологии, “узоры”.
Самое последнее использование КА (КА и Internet)
Какие бы тенденции ни наблюдались в развитии информационных технологий, тем не менее сегодня даже в области Интернета можно найти применение для этих всемогущих моделей (КА). Приведем два самых последних примера.
В 1996 г. одна уважаемая западная компьютерная компания (входящая в пятерку крупнейших в мире) приступила к моделированию развития глобальных сетей передачи данных на базе теории КА, создав для этой цели специальную лабораторию. Результатом такой работы должна стать математическая и программная модель, способная прогнозировать развитие трафиков в сети Интернета и планировать изменения сетевых ресурсов.
В 1980 - 1990 гг. в России широко применялись модели КА при разработке суперкомпьютеров на параллельной архитектуре (см. PC Week/RE, № 50/97, с. 57). А в 1986 г. группа российских исследователей, которой руководил автор статьи, открыла новый класс автоматов, получивших название ОКА (обобщенные КА). Наглядным примером эффективности нового аппарата моделирования служит написанная на языке Java система генерации неповторяющихся узоров с симметричной природой, которые могут стать основой изучения новых методов порождения изображений искусственной природы. Пример такого КА можно найти на сервере компании ЛАНК www.lanck.ruInterbuag. Там же есть небольшой обзор по КА, электронная версия книги автора “Искусственные ограничения естественного интеллекта” и ссылки на ресурсы в Internet, где поддерживаются обсуждаемые в данной статье вопросы.
Заключение
Мы рассмотрели только несколько аспектов из обширной области - теории вычислительных систем - и показали, что привычные нам компьютеры - не больше, чем очередной этап развития теории последовательных алгоритмов. Что будет следующим витком “гонки” гигантов компьютерной индустрии, пока не ясно, но в том, что в обозримом будущем принципы, положенные в основу индустрии ПК, могут измениться, никто не сомневается. Вопрос заключается в том, с какого конца начнется наступление - со стороны новых языков программирования и инструментальных средств (на старой архитектуре) или со смены сердца ПК - процессора. Колоссальные ресурсы компьютерной индустрии и огромный потребительский рынок ПК и систем телекоммуникаций нацелены на извлечение денег из наших с вами карманов. Темпы развития аппаратных средств (закон Мура - удвоение мощности процессора каждые 18 месяцев) впечатляют, однако мир, окружающий нас, намного разнообразнее и сложнее, чем прибор за 1000 долларов, и автор не сомневается, что настанет время, когда ваш ПК действительно станет “интеллектуальным усилителем“, и не последнюю роль в этом процессе могут сыграть те, кто сейчас учится в школе и решает простые с виду задачки типа игры “Жизнь”.
К автору можно обратиться по адресу: bva@lanck.ru или www.lanck.ru.
