5. Ячейковые автоматы

Исходник: Глава 5 Ячейковые автоматы

Переводчик: Wizardforcel

Лицензия: CC BY-NC-SA 4.0

Гордо использует Google Translate

Ячейковый автомат (CA) представляет собой модель мира с очень простыми физическими законами. "Ячейка" означает, что мир разделён на множество маленьких областей, называемых ячейками. "Автомат" — это машина, выполняющая вычисления; она может быть реальной машиной, но чаще всего "машина" является математическим абстрактным понятием или компьютерной симуляцией.

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

Я обсуждаю значение этих результатов и в конце главы привожу методы эффективной реализации CA на Python.

Код данной главы находится в файле chap05.ipynb в репозитории книги. Дополнительная информация о использовании кода представлена в Главе ?.

5.1 Простейший CA

Ячейковый автомат управляет правилом, которое определяет, как система развивается мгновенно. Время делится на дискретные шаги, а правила указывают, как рассчитывается состояние мира на следующий временной шаг на основе текущего состояния.> множественное число от automaton — automatons или automata.

Как пример, рассмотрим ячейковый автомат с одной ячейкой. Состояние ячейки представлено целым числом, записанным через переменную xi, где индекс i указывает, что xi является состоянием системы на временном шаге i. Как начальное условие, мы принимаем x0 = 0.

Теперь нам нужна некоторая логика. Я выберу случайное правило xi = x[i-1] + 1, что означает, что после каждого временного шага состояние CA увеличивается на единицу. На данный момент у нас есть самый простой CA, который выполняет простое вычисление: он считает.

Однако этот CA нереалистичен; количество возможных состояний обычно ограничено. Чтобы сделать его более реалистичным, я выберу минимальное количество интересных состояний 2 и ещё одно простое правило xi = (x[i-1] + 1) % 2, где % — оператор остатка (или модуль).

Поведение этого CA очень просто: оно мигает. То есть, после каждого временного шага состояние клетки меняется между 0 и 1.

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

5.2 Эксперименты ВольфрамаВ предыдущем разделе клеточное автоматическое поле состояло всего из одной клетки, поэтому его можно рассматривать как нулевую размерность, что делает его не слишком интересным. В остальной части этой главы мы будем исследовать одномерные (1-D) клеточные автоматы, которые становятся очень интересными.Когда говорят о размерности клеточных автоматов, имеют в виду, что клетки расположены в некотором пространстве таким образом, чтобы некоторые из них могли считаться "соседями". В одномерном случае существуют три естественные формы:

Ограниченная последовательность:

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

Цикл:

Конечное количество клеток располагается в виде цикла. У всех клеток есть два соседа.

Бесконечная последовательность:

Бесконечное количество клеток располагается в ряд.

Правила, определяющие мгновенную эволюцию системы, основаны на концепции "окрестности", то есть группы клеток, которая определяет следующее состояние данной клетки.

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

Эксперименты Вольфрама использовали окрестность из трёх клеток: саму клетку и её соседей слева и справа.

В этих экспериментах каждая клетка имела два возможных состояния, представленных цифрами 0 и 1 соответственно, поэтому правила можно было свести к таблице, отображающей состояние окрестности (тройку состояний) в следующее состояние центральной клетки. Ниже приведена примерная таблица:| prev | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | next | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |

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

Таблица 5.1: Состояние правила 50 после десяти временных шагов

Вышеуказанное изображение демонстрирует эффект правила 50 после десяти временных шагов. Первая строка представляет состояние системы на первом временном шаге; она начинается с "включенной" клетки, а все остальные — "выключенными". Вторая строка представляет состояние системы на следующем временном шаге и так далее.

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

5.3 Классификация клеточных автоматов (КА)

Рисунок 5.2: Правило 18 после 64 шагов

Сколько существует различных клеточных автоматов?

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

Первый эксперимент Wolfram с клеточными автоматами заключался в тестировании всех 256 возможностей и попытках классифицировать их.

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

Примером второго класса является правило 50. Оно создаёт простой шаблон с вложенными структурами; другими словами, этот шаблон содержит множество своих меньших версий. Правило 18 делает эти вложенные структуры ещё более явными; Рисунок 5.2 показывает состояние после 64 шагов.Эта модель напоминает треугольник Серпинского, который вы можете прочитать здесь: http://en.wikipedia.org/wiki/Sierpinski_triangle.

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

5.4 Случайность

Рисунок 5.3: Правило 30 после 100 шагов

Третий класс включает клеточные автоматы, которые порождают случайность. Примером такого автомата является правило 30; Рисунок 5.3 показывает его состояние после 100 временных шагов.

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

Программы, которые производят числа, которые выглядят случайными, называются псевдослучайными генераторами чисел (PRNG). Они не считаются истинно случайными, потому что:

• Многие из них генерируют регулярные последовательности, которые могут быть обнаружены статистически. Например, первоначальное реализация rand в C стандартной библиотеки использовала линейный конгруэнтный метод, который генерирует последовательности с легко обнаруживаемыми корреляциями.+ Любое использование ограниченного состояния (то есть хранящегося объёма данных) Pseudo-Random Number Generator (PRNG) рано или поздно повторится. Одним из характеристик таких генераторов является периодичность этого повторения. Основной процесс ниже практически детерминирован, что отличает его от некоторых физических процессов, таких как радиоактивное распадение и тепловой шум, которые считаются базово случайными.

Современные псевдослучайные генераторы (PRNG) производят последовательности, статистически неразличимые от случайных значений, и они реализуются с очень длинными периодами, такими, что Вселенная рухнет до повторения. Существование этих генераторов поднимает вопрос о том, существует ли реальная разница между качественной псевдослучайной последовательностью и последовательностью, созданной "настоящим" случайным процессом. В книге "Новый вид науки", Уолфрам считает, что такой разницы нет (страницы OnClickListener 315–326).

5.5 Детерминизм

Существование третьего типа клеточных автоматов является неожиданностью. Чтобы показать, насколько это неожиданно, позвольте мне начать с философского детерминизма (детерминистской позиции) (см. http://en.wikipedia.org/wiki/Determinism). Многие философские позиции трудно точно определить, поскольку у них есть различные вариации. Я часто нахожу полезным использовать список заявлений, расположенных от слабого до сильного, чтобы определить их:Детерминированные модели могут делать точные прогнозы для некоторых физических систем.

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

Все события вызваны предшествующими событиями, но многие физические системы по сути дела непредсказуемы.

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

Целью моей концепции этого спектра было сделать D1 таким слабым, чтобы почти каждый человек мог принять его, а D4 таким сильным, чтобы почти никто не мог принять его, и некоторые люди могли бы принять промежуточные заявления.

Как ответ на историческое развитие и научные открытия, центр масс общественного мнения колебался по этому спектру. До научной революции многие люди верили, что работа Вселенной в целом была непредсказуемой или контролировалась сверхъестественными силами. После победы новотоновой механики некоторые оптимисты начали верить в вещи, подобные D4; например, Пьер-Симон Лаплас в 1814 году написал:> Мы можем рассматривать текущее состояние Вселенной как следствие прошлых событий и причин будущих событий. Интеллект, имеющий знание всех сил, движущих природу, и всех местоположений всех предметов природы в определенный момент времени, если этот интеллект будет достаточно велик, чтобы представить эти данные для анализа, он сумеет свести движения самых больших звезд и самых маленьких атомов в одну формулу; для такого интеллекта ничего не будет случайным, будущее будет таким же очевидным перед ним, как и прошлое. Подобное "разумное" существо называется "Дьяволом Лапласа". См. https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B2%D1%8B%D0%B9_%D0%B4%D0%B5%D0%BD%D1%8C_%D0%A0%D0%B0%D0%BD%D0%B4%D0%B5%D0%BB%D0%B0.

В данном контексте слово "дьявол" используется в значении "дух", а не как метафора злого существа.Открытия XIX и XX веков постепенно разрушали надежды Лапласа. Термодинамика, радиоактивность и квантовая механика представляют собой последовательные вызовы строгому детерминизму.

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

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

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

5.6 Космический корабль

Рисунок 5.4: Правило 110 после Yöntem 100 шаговПоведение четвёртого типа клеточных автоматов особенно удивляет. Несколько одномерных клеточных автоматов, среди которых наиболее известен правило 110, являются универсальными вычислителями, то есть они могут вычислять любую вычислимую функцию. Эта характеристика также называется универсальностью и была доказана Мэттом Койком в 1998 году. См. http://en.wikipedia.org/wiki/Rule_110.Рисунок ? показывает вид правила 110 при начальных условиях одного активированного клетки и 100 шагах:

Рисунок 5.5: Правило 110 при случайных начальных условиях и 600 шагах

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

Столкновения космических кораблей имеют различные результаты в зависимости от типа корабля и его фазы при столкновении. Некоторые столкновения уничтожают корабли, другие приводят к слиянию кораблей, а третьи вызывают изменения направления движения кораблей. Эти столкновения являются вычислительной основой правила КА 110. Если рассматривать корабли как сигналы, передающиеся через провода, а столкновения — как логические ворты для вычисления операций И и ИЛИ, то можно понять смысл того, как КА выполняют вычисления.

5.7 Общественность

Чтобы понять общественность, нам нужно понять теорию вычислимости, которая говорит о вычислительных моделях и том, что они могут вычислять.Одним из самых общих вычислительных моделей является машина Тьюринга, которую Алан Тьюринг представил как абстрактный компьютер в 1936 году. Машина Тьюринга представляет собой одномерное клеточное автоматическое поле с бесконечностью в обоих направлениях и добавленной головкой чтения/записи. В любое время головка находится над одной клеткой. Она может читать состояние этой клетки (обычно состояниями двух типов) и записывать новое значение в эту клетку.

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

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

Машина Тьюринга очень полезна, так как она позволяет описать набор функций, которые могут быть вычислены набором машин Тьюринга. Этот набор функций называется вычислимой функцией Тьюринга.Сказать, что машина Тьюринга может вычислять любую вычислимую функцию Тьюринга, это избыточно; по определению это верно. Но вычислимость Тьюринга интереснее этого.

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

Эта идея привела к Теории Чёрча-Тьюринга, которая, в основном, определяет, что значит быть вычислимым. Эта "теория" заключается в том, что вычислимость Тьюринга является правильной, или хотя бы естественной, определением вычислимости, поскольку она описывает мощь множества различных вычислительных моделей.

Правило КА 110 также является другой вычислительной моделью, отличающейся своей простотой. Оно тоже универсально и поддерживает Теорию Чёрча-Тьюринга.

В книге "A New Kind of Science", Уолфирамм развивает вариант этой теории, которую он называет "Принципом вычислительной эквивалентности": практически все непростые процессы можно рассматривать как вычисления одинаковой вычислительной сложности.Более конкретно, принцип вычислительного эквивалентия утверждает, что системы, найденные в природе, могут выполнять вычисления, достигающие самой высокой ("универсальной") степени вычислительной способности, и что большинство систем действительно достигает этой самой высокой степени вычислительной способности. Поэтому большинство систем являются вычислительно эквивалентными (см. [http://mathworld.wolfram.com/PrincipleofComputationalEquivalence.html]).When applying these definitions to cellular automata (CA), Class I and Class II behaviors are "明显简单". Class III may not be so obvious, but perfect randomness is in some sense just as simple as perfect order; complexity lies somewhere in between. So Wolfram claims that Class IV behavior is common in nature, and almost any system exhibiting it is computationally equivalent.

5.8 Подтверждаемость

По мнению Вольфрама, его принцип сильнее теории Черча-Тьюринга, так как он относится к реальному миру, а не к абстрактной модели вычислений. Однако говорить о том, что "натуральные процессы можно рассматривать как вычисления", кажется мне заявлением о выборе теории, а не просто гипотезой о мире природы.

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

Например, утверждение о том, что все формы жизни на Земле произошли от общего предка, является валидируемым, поскольку оно делает конкретные прогнозы о генетической схожести современных видов (включая других). Если мы найдём новый вид, ДНК которого почти совершенно отличается от нашей, это будет опровергать теорию общего происхождения (или, по крайней мере, вызывать вопросы).С другой стороны, так называемая "теория сотворения", согласно которой все виды были созданы сверхъестественной силой, является невалидируемой, потому что нет никаких наблюдаемых фактов, которые противоречили бы естественному миру. Любой результат эксперимента можно объяснить волей Создателя.

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

Например, если библейская теология верна, то какое практическое значение она имеет? Она не сообщает нам ничего о Создателе, кроме того, что Он "очень любил жуков" (по мнению Дж. Б. С. Халдана). В отличие от теории эволюционной общности, которая объясняет множество областей науки и биоинженерии, понимание этого мира или его использование не имеет значения.

5.9 Какова эта модель?

Рисунок 5.6: Логическая структура простой физической моделиНекоторые клеточные автоматы являются преимущественно математическими произведениями искусства. Они интересны тем, что удивляют, полезны, красивы или предоставляют инструменты для создания новых математических конструкций (например, теорема Church-Turing).Однако, вопрос остаётся открытым: являются ли они моделями физических систем? Если да, то они очень абстрактны, то есть они не слишком детализированы или реалистичны.

Например, некоторые виды конусных улиток производят узоры на своих ракушках, аналогичные тем, которые могут быть созданы с помощью клеточных автоматов (см. en.wikipedia.org/wiki/Cone_snail). Поэтому естественно предположить, что клеточный автомат служит моделью механизма, который создаёт узоры на ракушках при их росте. Однако, хотя элементы модели (так называемые клетки, коммуникация между соседними клетками, правила) должны соответствовать элементам растущего улитка (реальные клетки, химические сигналы, сети взаимодействия белков), это пока ещё не ясно.

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

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

Простые модели предлагают альтернативные объяснения по сравнению с подробными моделями. При использовании подробных моделей аргумент может выглядеть следующим образом: «Мы интересуемся физической системой S, поэтому мы создали подробную модель M, которую мы проанализировали и смоделировали. Это показывает, что M демонстрирует поведение B, которое схоже с наблюдаемым поведением O (как качественно, так и количественно) нашей системы. Почему же происходит O? Потому что S похожа на M, а B похожа на O, и мы можем доказать, что M приводит к B». Используя простую модель, мы не можем сказать, что S схожа с M, так как это не так. Вместо этого аргумент звучит следующим образом: "Есть группа моделей, которая делится общими характеристиками. Любая модель, имеющая эти характеристики, демонстрирует поведение B. Если мы наблюдаем явление O, аналогичное B, одним из способов его объяснить является то, что это указывает на наличие в системе S группы характеристик, достаточной для генерации 1.

Добавление большего количества характеристик не помогает. Увеличение реалистичности модели не делает её более надёжной; это просто маскирует различие между базовыми характеристиками, вызывающими O, и случайными особенностями системы S.Рисунок 5.7 показывает логическую структуру такой модели. Характеристики x и y достаточно для создания поведения. Добавление больше деталей, таких как характеристики w и z, может сделать модель более реалистичной, но эта реалистичность не увеличивает объясняющую силу.

5.10 Реализация КА

Рисунок 5.7: Список списков (слева) и массив NumPy (справа).

Для создания графиков в этой главе я создал Python-класс под названием CA, представляющий клеточные автоматы, а также класс для отображения результатов. В следующих разделах я объясню, как они работают.

Для хранения состояния КА я использую массивы NumPy — многомерные структуры данных, где все элементы имеют одинаковый тип. Они похожи на вложенные списки, но обычно занимают меньше места и работают быстрее. Рисунок 5.7 показывает причину. Левый рисунок представляет собой список списков целых чисел; каждый пункт представляет ссылку, которая занимает 4–8 байт. Чтобы получить доступ к одному из этих чисел, вам нужно последовать за двумя ссылками.

Правый рисунок показывает тот же набор чисел в виде массива. Поскольку все элементы имеют одинаковый размер, они могут быть расположены последовательно в памяти. Такое расположение экономит место, поскольку не используются ссылки, и время, так как можно сразу вычислить положение элемента по индексу; нет необходимости следовать за цепочкой ссылок.Чтобы объяснить работу моего кода, я начну с клеточного автомата (КА), который считает четность каждой клетки в окрестностях. Если число четное, его четность равна 0; если число нечетное, четность равна 1.

Сначала я создаю нулевой массив с единицей в середине первой строки.

>>> rows = 5
>>> cols = 11
>>> ca = np.zeros((rows, cols))
>>> ca[0, 5] = 1
print(ca)
[[ 0.  0.  0.  0.  0.  1.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]]

Функция plot_ca с помощью графика отображает результат.

import matplotlib.pyplot as plt

def plot_ca(ca, rows, cols):
    cmap = plt.get_cmap('Blues')
    plt.imshow(ca, interpolation='nearest', cmap=cmap)

Согласно соглашению, я использовал сокращённое имя plt, чтобы импортировать pyplot. Функция imshow рассматривает массив как "изображение" и выводит его. Используя цветовую карту 'Blues', "включённые" клетки отображаются в темно-синий цвет, а "выключённые" — в светло-синий.

Для вычисления состояния CA на следующем временном шаге можно использовать step:

def step(array, i):
    rows, cols = array.shape
    for j in range(1, cols - 1):
        array[i + 1, j] = sum(array[i, j - 1:j + 2]) % 2

Аргумент array представляет состояние CA с помощью NumPy массива. rows и cols — это размеры массива, а i — это индекс временного шага, который мы должны рассчитать. Я использую i для представления строки массива, которая соответствует времени, а j — для столбца, которая соответствует пространству.Внутри step, мы проходимся по элементам i-ой строки. Каждый элемент является суммой трёх элементов из предыдущей строки, взятых по модулю 2.

5.11 Взаимная корреляция

Функция step из предыдущего раздела довольно проста, но её скорость не самая высокая. Общее правило состоит в том, что если заменить цикл на операцию с массивами NumPy, то можно существенно увеличить производительность, так как циклы в Python могут вызывать значительные затраты времени. В этом разделе я покажу, как использовать функцию корреляции NumPy для ускорения шага.

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

Например, следующее окно выбирает первые три элемента:

>>> window = np.zeros(cols, dtype=np.int8)
>>> window[:3] = 1
>>> print(window)
[1 1 1 0 0 0 0 0 0 0 0]

Если мы умножим этот массив на последнюю строку, мы получим первые три элемента:

>>> print(array[4])
>>> print(window * array[4])
[0 1 0 0 0 1 0 0 0 1 0]
[0 1 0 0 0 0 0 0 0 0 0]

Теперь мы можем использовать sum и оператор модуль для вычисления первого элемента следующей строки:

>>> sum(window * array[4]) % 2
1

Если мы сместим окно вправо, оно выберет следующие три элемента, и так далее. Таким образом, мы можем переписать step следующим образом:```py

def step2(array, i): rows, cols = array.shape window = np.zeros(cols) window[:3] = 1 for j in range(1, cols): array[i, j] = sum(window * array[i-1]) % 2 window = np.roll(window, 1)

`roll` перемещает окно вправо (он также помещает последний элемент в начало, но это не влияет на работу этого функционала).

`step2` генерирует такой же результат, как и `step`. Он всё ещё не очень быстрый, но шаг в правильном направлении, так как мы только что выполнили операцию (умножение окна, суммирование результатов, смещение окна и повторение), которая используется во многих приложениях. Этот процесс называется взаимной корреляцией, а NumPy предоставляет функцию `correlate`, чтобы вычислить её.

Мы можем использовать её, чтобы написать более быструю и простую версию шага:

```py
def step3(array, i):
    window = np.array([1, 1, 1])
    array[i] = np.correlate(array[i - 1], window, mode='same') % 2

Когда мы используем np.correlate, окно не обязательно должно иметь ту же длину, что и массив, поэтому можно сделать окно проще.

Параметр mode определяет размер результата. Вы можете прочитать подробную информацию в документации NumPy, но когда режим равен 'same', результат имеет ту же длину, что и вход.

5.12 Таблица CA

Остался один шаг. Если правила CA зависят только от суммы соседних значений, то наши до сих пор функции работают, но большинство правил также зависит от того, какие именно соседние клетки активированы. Например, 100 и 001 могут давать разные результаты. ```Мы можем использовать окно со значениями [4, 2, 1], чтобы сделать `step` более универсальным, который будет интерпретировать окрестность как двоичное число. Например, окрестность 100 даёт 4; 010 — 2, а 001 — 1. Затем мы можем найти эти результаты в таблице правил.

Вот более общая версия шага:

def step4(array, i):
    window = np.array([4, 2, 1])
    corr = np.correlate(array[i - 1], window, mode='same')
    array[i] = table[corr]

Первые две строки почти такие же. Последняя строка находит каждый элемент corr в таблице и присваивает результат array[i].

Наконец, вот функция для создания таблицы:

def make_table(rule):
    rule = np.array([rule], dtype=np.uint8)
    table = np.unpackbits(rule)[::-1]
    return table

Аргумент rule является целым числом от 0 до 255. В первой строке правило помещается в односимвольный массив, чтобы мы могли использовать unpackbits, преобразуя номер правила в его двоичное представление. Например, вот таблица для правила 150:

>>> table = make_table(150)
>>> print(table)
[0 1 1 0 1 0 0 1]

Файл thinkcomplexity.py содержит определение CA, которое упаковывает код из этой главы, а также два класса для отрисовки CA, PyplotDrawer и EPSDrawer. ## 5.13 Упражнения

Упражнение 1

Код текущей главы находится в Jupyter-ноутбуке chap05.ipynb, расположенном в репозитории книги. Откройте этот ноутбук, прочтите код и запустите его. Вы можете использовать этот ноутбук для выполнения упражнений данной главы. Мои решения находятся в ноутбуке chap05soln.ipynb.### Упражнение 2

Это упражнение требует экспериментирования с правилом 110 и некоторыми его корабликами.

1. Прочтите страницу Википедии о правиле 110, где описано его фоновое изображение и кораблики: https://en.wikipedia.org/wiki/Rule_110.

2. Создайте клеточный автомат (CA) с использованием правила 110, используя начальные условия, которые приведут к стабильному фоновому изображению.

   Обратите внимание, что класс CA предоставляет метод start_string, который позволяет вам инициализировать состояние массива строкой из единиц и нулей.

3. Измените начальные условия, добавив различные паттерны в центральной части строки, и проверьте, какие из них создают кораблики. Для некоторых разумных значений ( n ) вы можете захотеть перечислить все возможные паттерны из ( n ) бит. Для каждого кораблика, сможете ли вы найти время и скорость его перемещения? Какое самое большое кораблико вы смогли бы найти?

4. Что происходит при столкновении двух корабликов?

Упражнение 3

Цель этого упражнения — реализовать машину Тьюринга.1. Прочтите статью http://en.wikipedia.org/wiki/Turing_machine, чтобы узнать больше о машинах Тьюринга.

1. Напишите класс Turing, который будет реализовывать машину Тьюринга. Для таблиц действий используйте правило Busy Beaver с тремя состояниями.

2. Напишите класс TuringDrawer, который генерирует изображение, представляющее состояние ленты, а также положение головки и её состояние. Пример внешнего вида можно найти здесь: http://mathworld.wolfram.com/TuringMachine.html.### Упражнение 4

3. Это упражнение требует выполнения и тестирования нескольких псевдо-случайных численных генераторов (PRNG). Для проведения тестов вам потребуется установить программу DieHarder, которую можно скачать с сайта https://www.phy.duke.edu/~rgb/General/dieharder.php. Возможно, она доступна как пакет для вашей операционной системы.

4. Напишите программу, которая реализует один из линейных конгруэнтных генераторов случайных чисел (LCG), описанных на странице http://en.wikipedia.org/wiki/Linear_congruential_generator. Проведите тестирование с помощью DieHarder.

5. Прочтите документацию модуля Python random. Какой PRNG используется в этом модуле? Проведите тестирование.

6. Реализуйте клеточный автомат (CA) с использованием правила 30, используя несколько сотен клеток. Запустите его на достаточном количестве шагов во времени, чтобы получить последовательность битов из центрального столбца. Проведите тестирование.

Упражнение 5

Доказуемость отрицания является привлекательной и полезной идеей, но она не считается универсальным решением границ в научной философии так, как это утверждалось Поппером. Прочтите http://en.wikipedia.org/wiki/Falsifiability и ответьте на следующие вопросы.1. Какова проблема границ?

1. Согласно Попперу, решает ли принцип фальсифицируемости проблему границ?
2. Приведите два примера теорий: одна считается научной, а другая — нет; они успешно различаются по критерию фальсифицируемости.
3. Вы можете сформулировать одно или несколько возражений, выдвинутых философами науки и историками на утверждения Поппера?
4. Есть ли у вас впечатление, что практические философы высоко ценят работу Поппера?