15 мая 2005

Два года назад вышла книжка Stephen Wolfram New kind of science http://www.wolframscience.com/nksonline/

Говорится в ней обо всем на свете, но я понял вот что.

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

Но есть очень простые системы, которые ведут себя очень сложно - непредсказуемо. Но правила, которым они подчиняются - чрезвычайно просты. Например, вот такой клеточный автомат, как внизу странички.. Пример взят из книжки Stephen Wolfram

Это правила, как клетки меняют свой цвет на каждом итакте - каждая клетка использует ту же систему правил. Со временем на плоскости возникают очень странное распределение черно-белых точек.

Основная идея, как я ее понимаю - случайные и простые - тоже случайные - правила могут порождать очень сложное поведение. Я как то писал по поводу примеров к своему курсу по FLASH - я сделал одну ошибку в программировании, и получил очень визуально-интересный результат. И естественным путем процессы могут так и протекать - очень простые правила, очень простые условия, и очень непростой результат. Например эволюция на земле.

Клеточные автоматы изучали давно. Но не обращали внимание на то, что они могут давать нечто непредсказуемое, а наоборот, фокусировались на понятном - клеточные автоматы могут имитировать с нашей точки зрения "разумное" поведение (Цетлин в ИПМ), или они могут давать результат, который мы от них хотим (а что то они в принципе не способны делать).

Вообще, книжка полна пафоса - восходящего к довоенным годам и к тезису Тьюринга - понятие "вычисление" совпадает с вычислениями на машине Тьюринга (с рекурсивными функциями, с алгоритмами Маркова, с машинами Минского, etc.). С этой точки зрения интересно построение универсального клеточного автомата и результаты (все на уровне картинок, чего и достаточно) моделирования разнообразных систем с помощью клеточных автоматов. Структура систем и начальные условия интерпретируются в терминах некоторых конфигураций закрашенных клеток, клеточные автоматы позволяют информации об этих структурах передаваться по плоскости … В поведении того, что претендует на универсальность (универсальный вычислитель), не должно быть сильно выраженной периодичности в конфигурациях. И автор предполагает, что сложное поведение клеточного автомата - признак универсальности, хотя, конечно, универсальность алгоритмически не распознается. Вообще есть целая иерархия вычислимых, но не рекурсивных множеств - степени рекурсивности.

Графика - продолжение кусков асфальта. И рисунок из книжки Stephen Wolfram New kind of science.

15 May 2005

Some words on cellular automata - after a book of Stephen Wolfram New kind of science (in Russian)

First two images - asphalt after the rain, processed. The last - from the mentioned book …