П С Скаков

http://is.ifmo.ru/misc2/_wolf_annot.pdf в Приложении этот файл как был скачан.

Ниже текст для комментариев и работы над книгой.

Аннотация

книги Wolfram S. A New Kind of Science. Wolfram Media, Inc., 2002

Написана П.С.Скаковым (СПбГУ ИТМО)

Глава 1. Основания нового вида науки.

В общих чертах о базовых идеях.

Предлагается описывать системы в науке не через математические формулы, как это делалось до сих пор, а через взаимодействие простых программ.

Таким образом, можно через простое описание легко получить сложное поведение системы.

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

Прошлые разработки. Описывается неспособность различных областей к развитию, которую следует преодолеть, используя новый вид науки: искусственный интеллект, искусственная жизнь, теория катастроф, теория хаоса, теория сложности, теория вычислительной сложности, кибернетика, теория динамических систем, теория эволюции, экспериментальная математика, фрактальная геометрия, общая теория систем, нанотехнология, нелинейная динамика, научные расчёты, самоорганизация, статистическая механика.

История личных исследований науки, отражённая в этой книге.

Глава 2. Решающее значение имеет эксперимент.

Поведение простых систем.

В отличие от доминировавших раньше математических методов, новый тип науки предлагается изучать через практические эксперименты с поведением простых программ на компьютере.

Рассматриваются одномерные клеточные автоматы с двумя состояниями и одной точкой в начальном состоянии.

Клеточный автомат - равномерный массив, где изменение состояния каждой клетки зависит только от соседних клеток (и, возможно, её самой), это правило одинаково для всех клеток.

Наблюдаются следующие поведения:

1) Монотонное.

2) Простое периодическое.

3) Создание регулярных вложенных структур (фракталов).

4) Сложное поведение, кажущееся хаотическим.

Необходимость 'новой интуиции'. Старая, основанная на математических представлениях, интуиция, как правило, даёт неправильные результаты в новом виде науки.

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

Глава 3. Мир простых программ.

Предполагается наличие общих свойств поведения у систем простых программ на разных базовых элементах.

Снова клеточные автоматы.

3.1.1. Все 256 возможных 1D бинарных клеточных автоматов (стр.53).

3.1.2. “Среднеарифметические 1D клеточные автоматы” (более двух состояний) - стр.60: 'не наблюдается существенно более сложное поведение'.

3.2. Движущиеся автоматы (влево и вправо) - стр.71.

Состояний два и одно измерение.

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

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

3.3. Машины Тьюринга (стр.78).

По ленте перемещается каретка, которая имеет несколько состояний. В зависимости от состояния каретки и клетки ленты под ней задаётся изменение текущей клетки, состояния и положения каретки.

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

3.4. Подстановочные системы (стр.82), их отображение в виде дерева (стр.84).

Преобразование ленты элементов. На каждом шаге каждый элемент заменяется некоторым множеством элементов, при выборе правила, возможно, учитываются соседние элементы.

3.5. Системы последовательных замен (стр.88).

Преобразование ленты элементов. Таблица замен. Лента сканируется в одном направлении и к ней последовательно пытаются применить каждое из правил замен: производится попытка применить второе правило, только если первое невозможно применить на всей ленте.

3.6. Ленточные (цепочечные)системы (стр. 93).

Преобразование ленты элементов. Из начала ленты извлекается некоторое фиксированное количество элементов и в зависимости от него (по правилам замены) в конец ленты записывается некоторое заданное множество элементов.

3.7. Циклические ленточные системы (стр.95).

Похоже на предыдущую систему, но правила замены извлечённых элементов в добавляемые периодически меняется.

3.8. Регистровые машины (стр.97).

Имеется набор регистров, которые могут хранить неотрицательные числа. Для каждого из регистров имеется две команды: "увеличение на 1" и "если в регистре не 0, то уменьшение значения регистра на 1 и переход на команду номер N".

3.9. Символические системы (стр.102).

Выражения, обрабатываемые Mathematica. Пример: e[x_][y_] -> x[x[y]] применённое к e[e[e][e]][e][e].

Некоторые выводы.

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

Как были сделаны эти выводы.

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

Глава 4. Системы, основанные на числах (стр.115).

4.1. Существенность представления числа как набора цифр некоторой системы счисления.

4.2. Сложное поведение двоичного представления чисел при последовательном применении простых операций(стр.117): инкремент, умножение, рекурсивные соотношения – ряд Фибоначчи (стр.128).

4.3. Простые числа (стр.132), математические константы (пи, квадратные корни), математические функции, последовательные отображения как примеры систем со сложным поведением. Теория хаоса.

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

Глава 5. Двумерные системы и большая размерность (стр.169).

5.1. Приводятся примеры 2D (в частности, совпадает с некоторыми результатами из http://is.ifmo.ru/works/klet/)и 3D среднеарифметических клеточных автоматов.

5.2. 2D машин Тьюринга.

5.3. 2D подстановочные системы.

5.4. Сетевые системы (стр.193), как пример независимости от геометрии пространства.

5.5. Многопутевые системы (стр.204) - независимость от состояния во времени. Недетерминированные сетевые системы.

5.6. Системы, заданные наложенными ограничениями (стр.210).

Выводы. Несмотря на то, что некоторые эффекты возможны только в двумерном и более высоких размерностей пространствах, увеличение размерности не приводит к принципиальному росту сложности систем.

Глава 6. Начиная со случайности (стр.223).

6.1. Рассматривается поведение 1D клеточных автоматов при случайном начальном

состоянии.

Выделяются четыре класса поведения:

1) Переход в равномерное состояние.

2) Сохранение нескольких простых (возможно, периодических) структур.

3) Сложное поведение без видимой закономерности.

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

Приведено несколько примеров 1D трёхцветных среднеарифметических клеточных автоматов, чёткое отнесение которых только к одному из классов затруднено.

2D клеточные автоматы проявляют сходное поведение, пример 2D клеточного автомата четвертого класса - игра Жизнь.

6.2. Влияние небольшого изменения начального состояния, типичное поведение (стр.250), на примере 1D:

1) Игнорируется.

2) Вызывает изменение строго ограниченной области.

3) Изменения распространяются по всей области.

4) Изменения распространяются сложным образом, не обязательно по всей области.

Делается вывод, что класс поведения определяет возможности по распространению информации:

1) Не распространяется.

2) Распространяется только в пределах небольшой, строго определённой области.

3) Всегда распространяется по всему пространству.

4) Может распространяться на большие расстояния, но не обязательно по всему пространству.

6.3. Ограниченные системы (закольцованное пространство) (стр.255) проявляют поведение только первого и второго классов, так как число состояний конечно, а значит, периодическое повторение обязательно наступит.

6.4. Случайность (сложность) в системах с поведением третьего класса (стр.261) не всегда наблюдается при неслучайных начальных условиях (например, при низкой плотности точек одного типа относительно другого): некоторые клеточные автоматы порождают только регулярные вложенные структуры и наблюдается хорошо различимые их комбинации, а не случайное (сложное) поведение.

6.5. При специально подобранном, в частности, строго периодическом начальном состоянии можно получить поведение первого и второго классов для любого клеточного автомата (стр.266).

6.6. Локальные структуры в системах четвёртого класса (стр.281), как правило, исчезают через некоторое количество шагов. Но ключевой особенностью систем четвёртого класса является возможность существования в них бесконечно существующих структур и перемещающихся структур. Таким образом, системы четвертого класса могут проявлять элементы поведения всех остальных классов. Приведён пример структуры, порождаемой клеточным автоматом 110 при случайном зародыше. 110 – один из 256 автоматов, порождаемых 1D бинарным клеточным полем. 110 – это десятичное представление транспонированного столбца значений таблицы переходов (Qi+1(t) Qi(t) Qi-1(t) –> Qi(t+1)), которая записана в порядке

убывания двоичных значений комбинации входных воздействий: 0110 1110.

7. Механизмы в программах и природе (стр.297).

Предполагается, что системы в природе проявляют такое же поведение, как и системы простых программ.

Существует три механизма случайности:

1) Случайность присутствует на каждом шаге системы, возможно, вносится окружающей средой (стр.301).

2) Случайность присутствует только в начальном состоянии системы (стр.304)(теория хаоса).

3) Случайность как результат сложности внутреннего поведения системы (стр.315).

Феномен непрерывности (стр.327) - многие процессы нам кажутся непрерывными потому, что мы не точно рассматривает состояния системы. Предполагается, что изучение систем, в которых происходят дискретные изменения (как, например, кипение воды при непрерывном увеличении её температуры) лучше проводить на дискретных моделях.

В физике часто система описывается через ограничения, наложенные на её поведение, но такие системы не только сложно построить, но и они не проявляют сколько-нибудь сложного поведения (стр.342).

8. Применение в обычных системах (стр.363).

Рассматривается похожесть результатов работы систем простых программ на: рост кристаллов, разрыв материалов, течение жидкости, различные биологические объекты (окраска животных, строение листьев, ...), финансовые системы.

9. Фундаментальная физика (стр.433).

Обратимость: строится обратимый клеточный автомат (в том смысле, что по текущему состоянию можно прямо построить предыдущее, а не только следующее) со сложным поведением (стр.437).

Необратимость и второй закон термодинамики (стр.441): на примере построенного клеточного автомата показывается, что из того, что при различных обычных начальных условиях энтропия возрастает, не следует, что невозможно создать такие условия, когда она будет уменьшаться со временем.

Сохранение количественных характеристик и непрерывность (стр.458).

Модели пространства и времени на основе сетей и многопутевых систем.

Моделирование элементарных частиц (стр.525) и гравитации (стр.530).

10. Процессы восприятия и анализа (стр.547).

Вопрос определения 'случайность'. Предлагается использовать в варианте 'неупрощаемость'. На основе этого показывается случайность наблюдаемого сложного поведения систем простых программ.

Утверждается несовершенство наших способов восприятия (зрение, слух) и анализа информации (в том числе, рассматривается криптоанализ, математические формулы, образное мышление человека) - их недостаточно для получения простых результатов о состоянии системы простых программ. Возможно, в будущем мы овладеем более высокими формами восприятия.

11. Нотация вычислимости (стр.637).

Предлагается анализировать системы не через какие-то классические математические описания, а на основе понятия вычислимость.

Строится универсальный клеточный автомат (19 цветов), способный эмулировать работу любого 1D бинарного клеточного автомата (стр.645).

Показывается возможность эмуляции на клеточных автоматах других систем (машины Тьюринга, ...) (стр.656) и клеточных автоматов на других системах (стр.664).

Доказывается вычислительная эквивалентность 1D бинарного клеточного автомата 110 машине Тьюринга (стр.675). Программа машины Тьюринга – это начальное состояние поля клеточного автомата.

Предполагается, что универсален (= способен эмулировать все другие) любой автомат с четвертым типом поведения (стр.691).

12. Принцип вычислительной эквивалентности (стр.715).

Любая система, демонстрирующая поведение более сложное, чем монотонное или простое повторение /создание регулярных вложенных структур – является универсальной вычислительной системой. Существует только один разряд сложности вычислений, которые могут быть физически получены.

Принцип вычислительной несократимости (стр.737) - зная правила поведения системы и начальное состояние, в общем случае невозможно предсказать состояние системы, используя меньше вычислительных ресурсов, чем сама система при переходе в заданное состояние.

Свободная воля как следствие принципа вычислительной несократимости (стр.750).

Применение к математике (стр.772).

Размышления о других формах разума (стр.822).

Позитивные размышления о будущем технологии, негативные о возможностях развития науки (стр.840).

+350 страниц комментариев к книге.