Итак, всем привет!
Меня зовут Антон Матвеев, это моя первая статья и я хочу поведать вам о моем проекте, научной работе, я не знаю как это назвать, но его тема "Клеточные Автоматы" и я разобью это на несколько частей.
1. Краткая история клеточных автоматов
2. Код Вольфрама и Простейшие Клеточные автоматы
3. Тьюринг полные автоматы
4. Игра Жизнь
5. Код "Игры Жизнь"
Что же такое Клеточные автоматы?
Клеточный автомат - это дискретная модель, изучаемая в физике, математике, теории вычислимости, теоретической биологии и микромеханике.
Клеточные автоматы включают регулярную решётку ячеек, каждая из которых может находиться в одном из конечного множества состояний, таких как 1 и 0. Также решетка может быть любого размера.
Я часто видел, когда сёрфил интернет множество видеороликов и картинок насчет "Игры Жизнь" и я очень зарнтересовался этой темой, мне было интересно, что это вообще такое?
Сегодня я хочу вам рассказать о частичной истории Клеточных Автоматов.
Первый клеточный автомат:
Первый клеточный автомат появился благодаря Станиславу Уламу и Джону фон Нейману:
Станислав Улам, работая в Лос-Аламосской национальной лаборатории в 1940-е годы, изучал рост кристаллов, используя простую решёточную модель. В это же время Джон фон Нейман, коллега Улама, работал над проблемой самовоспроизводящихся систем. Первоначальная концепция фон Неймана основывалась на идее робота, собирающего другого робота. Такая модель известна как кинематическая. Разработав эту модель, фон Нейман осознал сложность создания самовоспроизводящегося робота и, в частности, обеспечения необходимого «запаса частей», из которого должен строиться робот. Улам предложил фон Нейману использовать более абстрактную математическую модель, подобную той, что Улам использовал для изучения роста кристаллов. Таким образом возникла первая клеточно-автоматная система. Подобно решётке Улама, клеточный автомат фон Неймана двухмерный, а самовоспроизводящийся робот описан алгоритмически. Результатом явился универсальный конструктор, работающий «внутри» клеточного автомата с окрестностью, включающей непосредственно прилегающие ячейки, и имеющего 29 состояний. Фон Нейман доказал, что для такой модели существует паттерн, который будет бесконечно копировать самого себя.
Простыми словами говоря они создали робота, который копирует сам себя.
Дальше в эти же 1940-е годы, Норберт Винер и Артуро Розенблат разработали клеточно-автоматную модель возбудимой среды. Целью было математическое описание распространения импульса в сердечных нервных узлах. Их оригинальная работа продолжает цитироваться в современных исследованиях по аритмии и возбудимым средам.
В 1960-е годы клеточные автоматы изучались как частный тип динамических систем, и впервые была установлена их связь с областью символьной динамики. В 1969 году Г. А. Хедланд провёл обзор результатов, полученных в этом направлении. Наиболее значимым результатом явилось описание набора правил клеточного автомата как множества непрерывных эндоморфизмов в сдвиговом пространстве.
В 1970-е получила известность двухмерная клеточно-автоматная модель с двумя состояниями, известная как игра «Жизнь». Изобретенная Джоном Конвеем и популяризованная Мартином Гарднером, она использует следующие правила: если клетка имеет двух «живых» соседей, она остаётся в прежнем состоянии. Если клетка имеет трёх «живых» соседей, она переходит в «живое» состояние. В остальных случаях клетка «умирает». Несмотря на свою простоту, система проявляет огромное разнообразие поведения, колеблясь между очевидным хаосом и порядком. Одним из феноменов игры «Жизнь» являются глайдеры - сочетания клеток, движущиеся по сетке как единое целое. Возможно построить автомат, в котором глайдеры будут выполнять некоторые вычисления, и впоследствии было показано, что игра «Жизнь» может эмулировать универсальную машину Тьюринга.
В 1969 году немецкий инженер Конрад Цузе опубликовал книгу «Вычислимый космос», где выдвинул предположение, что физические законы дискретны по своей природе, и что вся Вселенная является гигантским клеточным автоматом. Это была первая книга из области, называемой сейчас цифровой физикой.
В 1983 Стивен Вольфрам опубликовал первую из серии статей, исследующих очень простой, но до сих пор неизученный класс клеточных автоматов, называемых элементарными клеточными автоматами. Неожиданная сложность поведения этих простых автоматов привела Вольфрама к предположению, что сложность естественных систем обусловлена сходным механизмом. Кроме того, в течение этого периода Вольфрам формулирует концепцию истинной случайности и вычислительной неприводимости, и выдвигает предположение, что Правило 110 может быть универсальным - факт, доказанный в 1990 году ассистентом Вольфрама Мэтью Куком.
В 2002 году Вольфрам публикует 1280-страничный текст «Наука нового типа», где широко аргументирует, что достижения в области клеточных автоматов не являются изолированными, но весьма устойчивы и имеют большое значение для всех областей науки.
11-го ноября 2002 года Пауль Чепмен построил модель Жизни, которая является Регистровой Машиной Минского. Фактически Регистровая Машина Минского эквивалентна машине Тьюринга.
Первая версия образца была большой (268’096 живых ячеек на площади 4,558 x 21,469 клеток) и медленной по тем меркам (20 поколений/секунду при использовании "Life32" Иогана Бонтеса на 400 MHz AMD K6-II). Таким образом, в игре Жизнь можно выполнить любой алгоритм, который можно реализовать на современном компьютере.
Половина информации была взята из википедии, половина отрыта из других источников и подстроена под мой проект.
В следующей части я расскажу максимально просто и понятно о простейших клеточных автоматах и о коде Вольфрама.
Спасибо за то, что прочли мою статью! <3