Железная дорога Тьюринга

[spamsink]

Сегодня я узнал, что (игрушечная) железная дорога с одним паровозиком эквивалентна машине Тьюринга, если в наборе есть стрелки трех видов:

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

Comments

[dvv.livejournal.com]

👍

[con-vertor.livejournal.com]

this is fucking awesome!

[spamsink]

Это я по ссылкам при чтении про Wireworld нашел (о котором знал раньше, и даже писал, если мне память не изменяет, но не упоминал правильного названия, поэтому найти не могу).

Для справки:
http://en.wikipedia.org/wiki/Wireworld
http://www.quinapalus.com/wi-index.html
http://www.rezmason.net/wireworld/ (этого я раньше не видел: симулятор компьютера, вычисляющего простые числа, ~10 тыс. тактов - 2, ~35 - 3, ~100 - 5, и т.п.)

[1500py470.livejournal.com]

Во времена СССР выпустили 1801ВП124 для построения мп техники с использованием математики на основе ряда фибоначи, но вычисления на основе паровозика это намного ближе дэ инкредибал машинс :))

[spamsink]

Где было нужно такое кодирование, в котором нельзя две единицы подряд?

[1500py470.livejournal.com]

Для построения и обработки сигналов с быстродействующих ацп с применением не прецизионых резисторов 5-20 процентов

[1500py470.livejournal.com]

А ещё применяли для самосинхронизируещейся записи чтении на магнитные ленты и передаче по оптике

[spamsink]

Странно. Обычно для подобного используется просто таблица перекодировки типа "8 в 14".

[1500py470.livejournal.com]

Сам видел в живуюна работе только в быстродействующих ацп, про использование для передачи даных только слышал, что в Киевском Модуле такое делали. Украина славна затейниками, то логическую серию 523 на тиристорах, да с 3-х фазным электропитанием изобретут, то майдан учинят :))

[spamsink]

А в чем преимущество для быстродействующих АЦП?

[1500py470.livejournal.com]

Ключевое с непрецезиоными резисторами. Для традиционой схемы с R/2R нужно добавить больше младших разрядов для компенсации технологических разбросов изготовления -> больше разрядов, больше время на считывание плюс время на обсчёт поправок. А при использовании значений резисторов по ряду фибоначи требуется один раз откалиброваться и записать поправочные коеф. При такой технологии как у нас была в 80е когда военные сидели на заводе в прибалтике и как ОДИН годный скоростной АЦП получался посылали гонца с ним на другой завод в изделее вставить это было спасительным решением. Возможно при развитой технологии это является извращением, но у нас в них толк знали :)) калибровка каждого ацп и прикладывание к нему своего пзу с коэф может изврат, но зато применимый для ритмичного серийного производства

[spamsink]

Сильно.

[vak]

Это ж можно построить компьютер из белковых молекул, чтобы одни белки по другим ползали.

[spamsink]

Ненадежное это дело.

[vak]

Есть мажоритарные схемы, самокорректирующиеся коды и другие хитрости.

[1500py470.livejournal.com]

Или на муравьях как у Терри Пратчета

[spamsink]

Муравьиный феромон годится для "ленивой" стрелки, а с другими будет проблема.

[winpooh.livejournal.com]

На муравьях вроде у Хофстадтера в "Goedel, Escher, Bach" было. Только не компьютер, а разумное существо.

[codedot.livejournal.com]

Да, системы взаимодействия и химические вычисления точно где-то рядом:

http://www.sciencedirect.com/science/article/pii/S1571066108004210

[codedot.livejournal.com]

Интересно.

Наверное, можно даже построить отображение этой структуры в жесткие комбинаторы естественным образом:

http://www.sciencedirect.com/science/article/pii/S1571066108001370

Забавная получилась бы статья.

[spamsink]

Неочевидно, как двунаправленность реализовать.