Большие системы. Связность, сложность и катастрофы - Касти Дж.
Скачать (прямая ссылка):
главы.
Сложность структуры больших систем
121
где Uз - триггер с тремя состояниями, a D\ - автомат задержки на 1 шаг.
Тогда
0(/) = #о(/5)
для всех (fs - это полугруппа автомата f).
Замечания. 1. Согласно теореме 4.1, функция групповой сложности является,
по существу, единственной функцией, удовлетворяющей аксиомам сложности и
данной нормализации. Для любой другой функции, удовлетворяющей аксиомам,
должно выполняться неравенство
#0'(/X #0 (/) Для всех f^M^.
2. Автомат задержки на 1 шаг, так же как U3, является комбинаторной
подгруппой, действие которой задается следующим образом:
0,(а,( . . ., а") = а"_,, ?>, (а,) = null,
где {а", а"_ь ..., ai} -любая вводимая строка.
3. 0(/) = О тогда и только тогда, когда f представляет собой
последовательно-параллельно соединенные автоматы U3 и Di.
4. Для того чтобы показать, что существуют автоматы любого уровня
сложности, рассмотрим автомат
U = {а, Ь, с}, r={o, 1},
Q = {l,2,...,n}?
A (i, a) = i + l(mod n)f (=1,2,..., rt,
A(l, b) = 2,
A(2,b) = l,
A (x,b) = x, хф\,2,
A(l, c) = 2,
А(у,с) = у, уф 1,
S.(q, d).si.q(mod 2), qeQ, deU,
Используя вышеприведенные результаты и некоторые положения теории
полугрупп, можно показать, что сложность этого автомата
0 (С) = п - 1 независимо от начального состояния g^Q.
122
Сложность структуры больших систем
5. Нормализация U3 и D\ необходима в силу того, что они являются
самыми простыми объектами теории: ни один из этих автоматов не выполняет
вычислений и их действия полностью предсказуемы.
Нормализация напоминает известный в теории информации процесс выбора
событий, имеющих нулевое информационное содержание. Автоматы U3 и D\
действуют регулярно, от них нельзя ожидать каких-либо сюрпризов, и
поэтому их поведение не порождает информации. Следовательно, если
обнаруживаются подсистемы, которые ведут себя подобно триггерам, то они
могут быть удалены без изменения структурной сложности других подсистем,
несмотря на то что вычислительная сложность может уменьшиться.
ЭВОЛЮЦИОННАЯ СЛОЖНОСТЬ И ЭВОЛЮЦИОННЫЕ СТРУКТУРЫ
В качестве дискуссионного, но многообещающего примера использования
понятия сложности рассмотрим некоторые аспекты эволюции организмов с
учетом следующего принципа эволюции:
Организм в процессе эволюции претерпевает такие изменения, в результате
которых максимизируется контакт с окружающей средой в целях лучшего ее
понимания и разумного управления последней.
"Контакт с окружающей средой" измеряется объемом памяти, необходимой для
имитации поведения организма на компьютере, или, что то же самое, числом
триггеров, требуемых для построения автомата, имитирующего поведение
организма. Полный контакт с окружающей средой включает все формы контакта
как физические, та и мысленные. Когда говорят о "понимании и разумном
управлении окружающей средой", имеют в виду, что сложность взаимодействия
между организмом и средой достаточно высока и численно приблизительно
равна ' значению величины контакта. Можно показать, что увеличение
контакта вызывает соответствующее возрастание сложности, а так как
сложность тесно связана с пониманием (сложность - это минимальное число
координат, необходимых для описания процесса), то организм, имеющий такую
сложность в своих отношениях с внешней средой, должен ее понимать и быть
способен на нее воздействовать.
Таким образом, если организм может увеличить одновременно контакт,
управляемость, понимание и сложность, то это следует рассматривать как
прогресс в эволюции. Принцип эволюции как раз и формализует эти
эвристические доводы.
Сложность структуры больших систем
123
Перейдем к математическому описанию вышеприведенных явлений. Обозначим
через Et конечный автомат, представляющий окружение в момент t, а через
Ot- организм. Через Rt будем обозначать автомат, описывающий результат
взаимодействия организма Ot со средой Et (напомним, что результат
взаимодействия между двумя автоматами R представляет по определению
конечный автомат
R = (U, range б, range б, X, /),
где ranged - множество представлений устойчивых петель взаимодействия, а
ranged ranged-тождественное отображение). Далее положим С* =#(-/?*)-
количество состояний Rt, а с< = 0(/?<)+1 - функция сложности Rt,
увеличенная на единицу. Таким образом, Ct является контактным числом в
момент t, a ct - числом сложности.
ПРОБЛЕМЫ ВЫБОРА И СЛОЖНОСТЬ
На уровне личных или социальных проблем сложность тесно связана с
возможностью или невозможностью рационального выбора решений человеком. В
связи с этим сложность отражает тип неопределенности, который не
поддается обработке вероятностными методами.
Отличительной чертой сложности, присущей принятию решений, является
невозможность доказать существование функции, представляющей предпочтение
выборов. В этом смысле социальные проблемы выбора подобны проблемам,
возникающим перед игроком в шахматы, когда для поиска "удовлетворительной
стратегии" он должен решать проблему комбинаторной размерности. Однако
