Всем здравствуйте, я решил скомпоновать остальные 3 пункта в одну часть статьи.
Ссылка на прошлую часть: https://zen.yandex.ru/media/id/614e21541fa5b87eb505b944/kletochnye-avtomaty-ch-2-614e25a8d142f311b798c8a9
Сейчас я хочу рассказать вам о Тьюринг полных автоматах.
Тьюринг полные клеточные автоматы - это клеточные автоматы на которых можно производить математические вычисления.
Элементарные клеточные автоматы и игра жизнь (О которой я расскажу чуть позже) являются Тьюринг полными автоматами
Но также являются Тьюринговыми Болотами, потому что на них вычисления совершить настолько сложно, можно сказать что практически невозможно.
Но что если есть клеточный автомат который создан специально для математических вычислений? Такой полный по Тьюрингу автомат есть, он называется WireWorld. (https://danprince.github.io/wireworld/)
В этом клеточном автомате существует целых 4 типа клеток:
- Первый тип клеток - пустые клетки. Они нужны лишь для создания некого расстояния между проводами.
- Второй тип - сами провода, их обычно указывают желтым и они проводят сигнал. А работают они следующим образом:
Если клетка является клеткой провода и рядом с ней 1 или 2 соседа, то клетка тоже становится клеткой сигнала. И таким образом сигнал распространяется по проводу.
- Третий тип - сигнал, который распространяется по проводу.
- Четвертый тип - хвост, который следует за сигналом, как бы указывая направление сигналу.
Из этих простых правил можно без всяких проблем делать нужные структуры для вычислений. Также можно разобрать пару логических схем для понимания работы с этим автоматом:
Если выстроить две клетки по бокам провода, то можно сделать как бы препятствие сигналу на проводе, так как по правилам у клетки должно быть максимум 2 соседа:
Но если убрать клетку посередине, то можно получить что-то на подобии разветвителя:
А вот это что-то по типу диода. Пропускает сигнал с одной стороны и не пропускает с другой:
С помощью этого автомата можно собрать структуру, способную умножать два 8-битных числа:
А вот и полноценный компьютер:
В нем загружена программа для поиска простых чисел.
Начинается он с двойки как с первого простого числа, но ему нужно время, чтобы найти даже первое простое число.
Ещё можно воссоздать “реакции Белоусова Жаботинского в чашке Петри”:
Это как бы “Камень - Ножницы - Бумага”, потому что правила этого клеточного автомата - можно сказать “поедание” слабого цвета:
Зеленый перекрашивается в красный, красный перекрашивается в синий, синий перекрашивается в зеленый.
Теперь можно поговорить о "Игре Жизнь"
На эту тему я на Python написал небольшой код, для представления этого клеточного автомата.
На настоящий момент “Игра Жизнь” является самым популярным клеточным автоматом.
Его правила очень просты:
- У каждой клетки есть 8 соседних клеток.
- Клетка рождается если рядом есть 3 соседа и выживает если рядом есть 2 или 3 соседа.
Из таких правил и следует весь автомат.
Также есть много подвижных фигур:
-Глайдер
Вот ещё один осциллятор. Осциллятор - фигура, которая движется, но на одном месте в состоянии цикла:
Она поворачивается на 90 градусов каждый тик(Единица времени)
Ещё есть очень интересная структура под названием "Планерное ружье Госпера":
К этому типу я бы ещё отнес размножитель, он собран из нескольких ружий Госпера:
Сады Эдема
Моя любимая часть моего проекта. Во всех клеточных автоматах следуя правилам мы можем получить следующий шаг. Но далеко не всегда возможно получить предыдущий шаг, просто потому что просто не известно каким был предыдущий шаг, так как у него есть несколько вариантов.
Допустим в "Игре Жизнь" мы сталкиваем два глайдера и взависимости от того как они столкнулись, они могут исчезнуть совсем, превратиться в другие фигуры, но из этих фигур мы уже никак не узнаем, какими фигурами они были до этого, ведь они могли появиться разными способами. И получается, что эти клеточные автоматы как бы теряют информацию о своем прошлом, если у него вообще оно существовало.
Например вот эта структура является садом эдема для "Игры Жизнь":
Она никак не могла образоваться в нашем клеточном автомате если мы не задали её в начале, на самом первом шаге.
И получается что в таких клеточных автоматах есть всего один вариант будущего, но от нуля до нескольких вариантов прошлого, поэтому прошлое мы вычислить не сможем.
Это всё, что я хотел рассказать о клеточных автоматах, есть ещё разные соседства в Игре Жизнь, но по ним мало информации и добавлять их я не стал.
И вот ещё код Игры Жизнь: https://pastebin.com/Tbp6WsjM