WireWorld

[jayrandom]

Не могу не поделиться, потому что это красиво.

Помните клеточный автомат "Жизнь" Конвея?
После заражения ею в некоторых матшколах стала со страшной скоростью заканчиваться бумага в клетку. Писали на "линеечках" (даже матан!), а "клеточку" приберегали для Лайфа...

WireWorld - это тоже клеточный автомат с заранее заданным набором правил для всех клеток, где одной только топологией можно cмоделировать любую схему из цифровой электроники. И визуально наблюдать за тем, как там электроны бегают :)

Эта хрень ещё и полна по Тьюрингу! Впрочем, это наверное по транзитивности - поскольку цифровая электроника должна быть полна по Тьюрингу (в свою очередь потому, что собранные на ней процессоры - полны).

Comments

[livelight]

Клёвая штука, спасибо!

По последней ссылке удивило, что у них AND такой кривой и несимметричный.

[livelight]

Ещё подумал. Непонятно насчёт тьюринговской полноты и возможности смоделировать любую булевскую функцию. Есть теорема, что система булевских функций полна, если каждого из 5-и определённых классов в ней есть хотя бы одна функция, не входящая в него. В том числе в класс T₀ - функций, не сохраняющих 0 (то есть, f(0,....0)=1). Однако, как ни конструируй схему в WireWorld, получив на вход одни нули, она и на выходе даст 0. То есть, не для любой булевской функции можно обойтись только входными битами, а надо как-то дополнительно оговаривать тактовый генератор или ещё какой-нибудь халявный источник единиц.