WireWorld

[jayrandom]

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

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

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

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

Comments

[livelight]

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

[jayrandom.livejournal.com]

Не сразу очевидно, что в случае разноцветного клеточного автомата считать за ноль или единицу. У WW ведь четыре цвета. И где там аргументы функции.

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

***

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

[livelight]

В том примере явно считается, что наличие электрона - 1, а его отсутствие - 0.
А в схеме умножателя входные сигналы, судя по картинке, подаются в виде наличия электронов на тех входах, где должно быть 1.

Насколько мне известно, в современной электронике скорость распространения сигналов по проводнику тоже весьма осязаема. Если мы делаем, скажем, гигабитный (а это далеко не предел в наше время) сетевой коммутатор, то поделив 3*10⁸ м/с на 10⁹ бит/с, получаем всего 0.3 м/бит - то есть, во внутренних цепях может одновременно помещаться несколько бит. И тогда мы должны или подолгу держать пришедшие сигналы в буферах, пока подбираем подходящий путь для пришедшего пакета, или так провести провода, чтобы, пока пакет по ним идёт ото входа, на выходе уже открылся нужный шлюз, определённый по указанному в пакете адресу.

[wizzard]

Так можно считать "через такт" и осциллятор использовать как источник единиц :) (если я правильно понимаю, о чем идет речь)

[livelight]

Угу, и я о том же. Без осциллятора не обойтись, и входы-выходы надо тщательно с ним синхронизировать.

[tk33.livejournal.com]

В реальном мире тоже нет электроники без цепи питания. Тактирование не обязательно. Закон сохранения энергии должен иметь место.