ПОИСК Статьи Рисунки Таблицы Исторические замечания и литература из "Машины клеточных автоматов" Клеточные автоматы изобретались много раз под разными названиями, и несколько отличающиеся друг от друга понятия употреблялись под одним и тем же названием. В чистой математике их можно обнаружить как один из разделов топологической динамики, в электротехнике они иногда называются итеративными массивами, а студенты младших курсов могут знать их как вид игры на домашнем компьютере. Их использовали и злоупотребляли ими не только междисциплинарные ученые, но и междисциплинарные болтуны. Они стали темой или поводом бесчисленных диссертаций. О них много говорилось и писалось, но до последнего времени никто в действительности не видел большинство из них. [c.12] Поскольку эти исторические замечания предназначены для того, чтобы помочь читателю, а не сбить его с толку, мы коснемся только тех тем, которые считаем непосредственно относящимися к целям этой книги. [c.12] В обычных моделях вычислений, таких как машина Тьюринга, различают структурную часть компьютера, которая фиксирована, и данные, которыми компьютер оперирует - они являются переменными. Компьютер не может оперировать своей собственной материальной частью он не может себя расширять или модифицировать, строить другие компьютеры. [c.12] Хотя фон Нейман был ведущим физиком в такой же степени, как и математиком, точные физические рассуждения отсутствуют в его работе по клеточным автоматам его больше интересовало редукционистское объяснение определенных аспектов биологии. Действительно, механизмы, которые он предложил для получения самовоспроизводящихся структур на клеточном автомате, сильно напоминают открытые в следующем десятилетии механизмы, которые на самом деле наблюдаемы в биологических системах. [c.13] В конце войны, коща фон Нейман создавал один из первых электронных компьютеров, немецкий инженер К. Цусе прятался от нацистов в Австрии там, в уединении на вершине горы, у него возникли наброски многих идей параллельной обработки, включая языки программирования высокого уровня и вычисляющие пространства [76] - т. е. клеточные автоматы. К. Цусе особенно интересовался численными моделями в механике, и физические мотивы играли основную роль в его работе. К несчастью, исторические обстоятельства воспрепятствовали более широкой известности его работ в то время. [c.13] Работа фон Неймана по самовоспроизводящимся автоматам была завершена и описана А. Берксом [68], который сохранил активный интерес к этой области на протяжении нескольких последующих лет. Его Очерки по клеточным автоматам [10] являются хорошим введением в вопросы о клеточных автоматах, которые ставились в годы формирования вычислительных наук. В той же среде, т. е. в группе компьютерной логики Университета шт. Мичиган, Дж. Голланд приступил к использованию клеточных автоматов в задачах адаптации и оптимизации [27 ] был разработан программный имитатор универсальных клеточных автоматов общего назначения. Месяцы работы с этим имитатором (см. [55]) убедили одного из авторов (Тоффоли) в необходимости более непосредственной и эффективной аппаратной реализации - машины клеточных автоматов. [c.13] Важные теоретические вопросы обратимости и вычислимости, затронутые Муром и Майхиллом [10], были наряду с другими исследованы А. Смитом [52], С. Аморозо [2] и В. Аладьевым [1) этот подход был продолжен и ныне процветающей японской школой (см. [40] и литературу к этой работе). [c.14] Игра Джона Конвея жизнь , представленная широкой общественности ведущим рубрику математических игр и развлечений в журнале Сайентифик Америкен М. Гарднером [20], некоторое время пользовалась популярностью, близкой к культу, и сделала выражение клеточные автоматы частью бытового жаргона целого поколения молодых ученых. [c.14] Мы интересуемся клеточными автоматами прежде всего как автономными системами, т. е. как мирами, замкнутыми в себе, а не как трансдьюсерами (системы, которые порождают постоянный выходной поток информации в ответ на постоянный входной поток). По этой причине мы совсем не будем касаться обширной литературы, посвященной итерационно-цепным массивам в контексте арифметических вычислений, обработки изображений и распознавания образов. В качестве введения в эти области и руководства к машинам, разработанным для этих более специализированных приложений, может быть использована книга Престона и Даффа Современные клеточные автоматы [46 ]. [c.14] Этот подход был использован для того, чтобы обеспечить предельно простые модели обычных дифференциальных уравнений физики, таких как уравнение теплопроводности, волновое уравнение [61] и уравнение Навье-Стокса [23, 18], которые могут мыслиться как предельные случаи исключительно простых процессов комбинаторной динамики. В частности, клеточные автоматы были созданы для того, чтобы дать точные модели динамики жидкостей, которые не только будят мысль, но и конкурентоспособны, по крайней мере в некоторых обстоятельствах, с точки зрения их вычислительной эффективности. [c.15] Бурно развивающийся раздел теории динамических систем изучает возникновение хорошо описанных коллективных явлений - упорядочение, турбулентность, хаос, нарушение симметрии, фрактальность и др. в системах, состоящих из большого числа частиц, взаимодействующих друг с другом нелинейно цели исследований и их математический аппарат здесь больше похожи на присущие макроскопической физике и материаловедению. Клеточные автоматы обеспечивают богатую и непрерывно растущую коллекцию типичных моделей, в которых эти явления могут быть изучены относительно легко [66, 15, 5]. Систематическое использование клеточных автоматов в этом контексте энергично проводилось С. Вольфрамом [70-73, 43] его сборник статей по теории и применениям клеточных автоматов [74] содержит обширную библиографию. [c.15] клеточные автоматы, по-видимому, нашли устойчивое (и все более важное) применение в качестве концептуальных и практических моделей пространственнораспределенных динамических систем, для которых физические системы являются первыми и наиболее важными прототипами. [c.15] Вернуться к основной статье