How to become an author
Search
Write a publication
Pull to refresh

Comments 34

Лучшая статья по клеточным автоматам, что я видел. Браво.
Total votes 11: ↑10 and ↓1+9

Просто потрясающе!


А вот этот

ca


… нужно будет сделать помедленнее и зеленым на черном фоне

Total votes 11: ↑11 and ↓0+11

Да нет, я к тому, что знаю чем заняться вечером, но всё равно спасибо

Total votes 5: ↑5 and ↓0+5
Тогда могу предложить реализовать затухающую яркость. Если состояние клетки не изменилось — она тускнеет.

Заставка из фильма

Total votes 9: ↑9 and ↓0+9
Теперь я знаю как бабушки генерируют узоры для вывязывания крючком кружевных салфеток под вазочки. А еще ковры на стенах тоже не без конечных, видимо, автоматов свои узоры получили. Правда там, видимо, эти конечные автоматы самозародились случайно и неосознанно в полных по тюрингу человеческих мозгах.
Total votes 3: ↑3 and ↓0+3

На мой взгляд, это ближе к узорам спицами(всякие там "норвежские"). Крючок, если не квадратную сетку вязать, более именно узорчат.

Total votes 1: ↑1 and ↓0+1

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

This comment wasn’t rated yet0
Не кажется, а точно.
Для полноты по Тьюрингу нужна бесконечная память.
Total votes 1: ↑1 and ↓0+1
Тогда нет ни одного полного по Тюрингу устройства во вселенной.
Если рассматривать мозги настолько изолированно (без тела, рук, органов восприятия, прямой кишки), то от мозгов действительно мало проку. Но если мозгу в его мясном экзоскелете разрешается хотя бы гадить кучками в произвольном порядке, то это вполне полная по Тьюрингу система. В практическом смысле. Про теоретические бесконечности — это уже, ИМХО, демагония.
Total votes 4: ↑3 and ↓1+2

Гадить кучками в произвольном порядке — это построить компьютер. Кучками можно выкладывать как схемы алгоритмов, так и сами данные, которые используются в вычислениях. Без внешних "кучек" мозг очень вряд ли тянет на то, чтобы быть Тьюринг-полным.

This comment wasn’t rated yet0
И всё же, если мы начинаем говорить про полноту по Тьюрингу какого-то материального объекта, то и компьютер обычный таковым свойством обладать не будет из-за заведомо небесконечной памяти. А если предположить, что память прилагается к компьютеру где-то сборку и бесконечна, как лента машины Тьюринга, то почему бы не считать дерьмицо нашего биореактора неотъемлемой частью человечества=). В любом случае выдумать, запомнить и воспроизвести алгоритм человек способен и вряд ли кто-то с этим будет спорить.
Так что либо мы признаём, что человек всё же полон по Тьюрингу, либо считаем эту концепцию чисто умозрительной теоретической, как ряд натуральных чисел, которых, как бы и нет, раз уж мы их все не можем выписать на бумажке=).
Total votes 1: ↑1 and ↓0+1

Хорошо, с этим я согласен. Но, помимо памяти, есть ещё один подвох. Точнее, может быть. А что, если нам кажется, что мы можем любой алгоритм воспроизвести? Вполне вероятно, что есть некоторый класс алгоритмов, который — по неведомо какой причине — не будет работать в нашей голове? Допустим, если какие-то последовательности данных будут заставлять нейроны реагировать таким образом, что данные будут искажаться, но мы этого не заметим.

This comment wasn’t rated yet0
А что именно наводит вас на такую мысль? Чем отличается суждение вида: «вполне вероятно, что x86 процессор не сможет выполнить некий класс алгоритмов. Допустим...».
И что самое интересное, нетрудно даже придумать класс алгоритмов, который не будет вычислим некоторым семейством процессоров ввиду, скажем, их жадности к той же памяти или производительности.
Очевидно, что большинство алгоритмов не вычислимо мозгом, хотя бы по причине его подверженности тривиальной усталости.

Простите, но я не принимаю ваш довод к построению барьера между естественным и искусственным вычислителем ввиду его надуманности и необоснованности. Приведите больше аргументов, которые нельзя обернуть в сторону той же x86 архитектуры=)
This comment wasn’t rated yet0
Клеточный автомат это свертка по нескольким фиксированным правилам. Сверточные нейросети работают по такому-же принципу, только там сила влияния регулируется в процессе обучения и правила не дискретные.
Интересовался обработкой изображений при помощи клеточных автоматов, кроме выделения контуров ничего не нашел.

Несколько недель играюсь с реккурентными сверточными нейросетями.
Теоретически, вычислительных возможностей у такого типа на порядки больше, чем у обычных сверток, но пока никакого прорыва нет.
Скорее всего, градиентный спуск тут вреден, надо будет совместить градиентный оптимизатор с генетическим алгоритмом.
Total votes 4: ↑4 and ↓0+4
Все-таки это не совсем свертка в традиционном понимании этого слова. Свертка — это линейная операция: значение клекти вычисляется как взвешенная сумма ее окрестности. Иными словами, влияние каждого соседа суммируется независимо от других соседей.

А здесь в качестве «ядра» выступает произвольная булева функция от 9 переменных. Линейных булевых функций от девяти переменных существуется всего лишь 2^10, в то время как количество всех функций от 9 переменных — 2^512.
Total votes 3: ↑3 and ↓0+3
Спасибо за статью. Я не специалист, посмотрел просто на красивые картинки в надежде на какой-то приближенный к жизни вывод: а зачем это все? Это можно как то апроксимировать на эволюцию человека? Типа мы сейчас прошли всего 500 итераций, и нам еще осталось 1500 до достижения пика развития? Или типа, вводим искусственный ген человека и всего за 8 поколений получаем стабильную мутацию.
Total votes 6: ↑3 and ↓30

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

Total votes 2: ↑2 and ↓0+2

Пожалуй самая интересная статья на хабре за последнее время. Спасибо!


PS Вспомнилось, как играли в "жизнь" в школе. В тетрадке в клетку.

Total votes 2: ↑2 and ↓0+2

Можно ещё попробовать выпускать несколько автоматов на одно поле и наблюдать, как они сражаются за пространство. В игрушке Powder Toy это реализовано, но там набор автоматов предопределён.

Total votes 2: ↑2 and ↓0+2
У одного австралийского фантаста упоминается универсальный клеточный автомат. По аналогии с универсальной машиной тьюринга, он может выполнять любые алгоритмы. Конфигурация клеток на поле задаёт программу и данные.

Уж не знаю, обнаружены ли такие автоматы в реальности.
Total votes 1: ↑1 and ↓0+1

Game of life внезапно и есть Turing complete


https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life


It is possible for gliders to interact with other objects in interesting ways. For example, if two gliders are shot at a block in a specific position, the block will move closer to the source of the gliders. If three gliders are shot in just the right way, the block will move farther away. This sliding block memory can be used to simulate a counter. It is possible to construct logic gates such as AND, OR and NOT using gliders. It is possible to build a pattern that acts like a finite-state machine connected to two counters. This has the same computational power as a universal Turing machine, so the Game of Life is theoretically as powerful as any computer with unlimited memory and no time constraints; it is Turing complete. In fact, several different programmable computer architectures have been implemented in Conway's Life, including a pattern that simulates Tetris.
Total votes 5: ↑5 and ↓0+5
А вот и пример программы на глайдерах:
Life in life

Total votes 5: ↑5 and ↓0+5
Глядя на полученные красивые узоры, можно ли сказать, что эксперимент доказывает возможность самопроизвольной эволюции Вселенной? Ну в смысле, взяли пространство и время, насыпали туда кварков, или иных первокирпичиков, стали быстро-быстро всё это трясти, и некий простой механизм (какой?) обеспечил генетическое выведение всё более сложных систем: элементарные частицы, атомы и т.д.?
Total votes 1: ↑1 and ↓0+1
Не уверен, что это корректно. Какие у элементарных частиц механизмы наследования признаков? Отбор положим есть, но наследственности нет.
Total votes 1: ↑1 and ↓0+1

Нет, в смысле — как одна частица может передать новосозданным свои свойства? Стабильность — это метод отбора, а не наследственности.

This comment wasn’t rated yet0
а наследственность это комбинация частиц в ядре. Почитайте про ядерные изомеры.
This comment wasn’t rated yet0

Здравствуйте, снова заинтересовался клеточными автоматами после вашей статьи.
Скажите, а для подготовки всего что выложили, вы реально использовали JS, или у вас есть аппаратно ускоренная реализация?


Я ночью накидал на webGL на компьютере с GT640 реализацию чисто воспроизведения, причем с шейдером в лоб, даже без оптимизаций после 199x199 пробегало 100 поколений за 8ms (отображал только результат прогона ста поколений, остальное работало циклически во фрэйм-буфере и получал 30-50fps).


Upd: GTX1060, 800x800, 1000 поколений во фрэйм-буфере, и рендер каждого последнего = 20fps (для не оптимизированного правила 3x3x2).


При такой скорости можно замахнуться и на 3x3x2 = 2^18 = 512x512 пикселей картинки в качестве правила. Правда, самое интересное, генетику я еще не реализовал.


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

Total votes 2: ↑2 and ↓0+2
Скажите, а для подготовки всего что выложили, вы реально использовали JS, или у вас есть аппаратно ускоренная реализация?

На чистом JS. Выкладываю пример для картинки «habr».

Здесь считает.
Запуск производится через консоль. Пишем в консоль evil(3000); и поехали. Туда же, в консоль, записываются массивы для «тепловой карты».
Считал в FireFox. Если считать автоматы с большим полем — Chrome перестает подавать признаки жизни. В FireFox появляется кнопка «Остановить это».

Здесь смотрим, что насчитало.
Total votes 1: ↑1 and ↓0+1
Sign up to leave a comment.

Articles

Show the best of all time
Unlock dark mode

Your account

Sections

Information

Services

Support
© 2006–2024, Habr