Клетъчен автомат

Част от а
конвергентна серия на

Математика
Икона math.svg
1 + 1 = 11
  • Байесовски
  • Аргумент за Страшния съд
  • Теория на информацията
  • Луис Карол (есперанто)
  • Математически заблуди
  • Пренаписване на метрична система
  • Без теореми за безплатен обяд
  • Философия на математиката
  • Доказателство
  • Доказателство за несъответствието на аритметиката
  • Радикален
  • Терезианска математика

ДА СЕ клетъчен автомат е модел, състоящ се от дискретен брой състояния в обикновена мрежа. Времето също е дискретно и състоянието на клетката във времетоте функция на състоянията на съседите си по времет- 1. Например вИграта на живота на Конуей, клетката може да бъде „жива“ (оцветена в черно) или „мъртва“ (оцветена в бяло, може да се приеме и като клетка, която просто не е там), след това клетката променя състояния въз основа на броя на живите клетки точно до то. Въпреки това могат да съществуват по-сложни правила, като например правила, които позволяват на клетките да бъдат в множество различни състояния, освен само „живи“ и „мъртви“ (обикновено представени от различни цветни клетки).


Съдържание

Връзка с еволюцията

Вижте основната статия по тази тема: Еволюция

Освен че са забавна математическа игра, някои модели в клетъчните автомати симулират възпроизвеждане и еволюция. Има много случаи на самовъзпроизвеждане на модели в клетъчните автомати, като първият е направен във вариант на клетъчния автомат на Джон фон Нойман. Този репликатор е много голям и отнема повече от 10 стъпки за репликация, но оттогава са открити и други модели, като веригите на Лангтън, обвивки, които се възпроизвеждат чрез удължаване на псевдопод. Една разновидност на това, evoloop, може да бъде видяна да се развива. Тъй като конкуренцията обикновено е за пространство, те се стремят към все по-малки и по-малки вериги. Evoloops може да се формира от случайни модели, теоретичен пример за абиогенеза .

Ричард Докинс също изследва клетъчните автомати като модел за еволюция в своята книга Слепият часовникар (1986).


Играта на живота на Конуей

„Пистолет за планер на Gosper“ в Game of Life: пример за прости правила, произвеждащи „планери“до безкрайност

Играта на живота на Конуей, разработена от Британски математик Джон Хортън Конуей през 1970 г., е един от най-известните примери за клетъчни автомати сред математиците и компютър отрепки. Той създава анимирани клетъчни модели, базирани на строг набор от правила:

  1. Всяка жива клетка с по-малко от двама живи съседи умира (поради самота).
  2. Всяка жива клетка с повече от три живи съседи умира (поради пренаселеност).
  3. Всяка жива клетка с двама или трима живи съседи живее непроменена до следващото поколение.
  4. Всяка мъртва клетка с точно трима живи съседи се превръща в жива клетка.

С други думи, за разлика от други клетъчни автомати, клетките в Играта на живота на Конуей имат само две състояния - живо и мъртво. Въпреки това са открити или проектирани много сложни моделиЖивот. На 23 ноември 2013 г. е построен изричен пример за репликатор в Играта на живота на Конуей, състоящ се от 145 306 живи клетки. В HighLife е намерен малък репликатор, базиран на различен механизъм, един от вариантите на Game of Life на Conway, където правилата по-горе са променени. Играта на живота на Конуей също е в състояние да създаде универсален компютър, универсален конструктор или дори напълно функционираща симулация на себе си.

Животът имитира „Живот“

През 2017 г. беше открито, че моделите на оцелатирания гущер (Тимонов характер) се променя, докато расте по начин, сравним с този на клетъчния автомат.