?

Log in

No account? Create an account

Железная дорога Тьюринга - Общество дровосеков Бердичева по изучению Мишны

(Recent Entries) (Archive) (Friends) (Profile)

May. 23rd, 2015

12:52 pm - Железная дорога Тьюринга

Previous Entry Share Next Entry

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

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


(19 comments | Leave a comment)

Comments:

[User Picture]
From:dvv
Date:May 23rd, 2015 08:36 pm (UTC)
(Link)

👍

(Reply) (Thread)
[User Picture]
From:con_vertor
Date:May 23rd, 2015 08:38 pm (UTC)
(Link)
this is fucking awesome!
(Reply) (Thread)
[User Picture]
From:spamsink
Date:May 23rd, 2015 09:10 pm (UTC)
(Link)
Это я по ссылкам при чтении про 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, и т.п.)
(Reply) (Parent) (Thread)
[User Picture]
From:1500py470
Date:May 23rd, 2015 09:09 pm (UTC)
(Link)
Во времена СССР выпустили 1801ВП124 для построения мп техники с использованием математики на основе ряда фибоначи, но вычисления на основе паровозика это намного ближе дэ инкредибал машинс :))
(Reply) (Thread)
[User Picture]
From:spamsink
Date:May 23rd, 2015 09:17 pm (UTC)
(Link)
Где было нужно такое кодирование, в котором нельзя две единицы подряд?
(Reply) (Parent) (Thread)
[User Picture]
From:1500py470
Date:May 23rd, 2015 09:24 pm (UTC)
(Link)
Для построения и обработки сигналов с быстродействующих ацп с применением не прецизионых резисторов 5-20 процентов
(Reply) (Parent) (Thread)
[User Picture]
From:1500py470
Date:May 23rd, 2015 09:35 pm (UTC)
(Link)
А ещё применяли для самосинхронизируещейся записи чтении на магнитные ленты и передаче по оптике
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 23rd, 2015 09:50 pm (UTC)
(Link)
Странно. Обычно для подобного используется просто таблица перекодировки типа "8 в 14".
(Reply) (Parent) (Thread)
[User Picture]
From:1500py470
Date:May 23rd, 2015 09:59 pm (UTC)
(Link)
Сам видел в живуюна работе только в быстродействующих ацп, про использование для передачи даных только слышал, что в Киевском Модуле такое делали. Украина славна затейниками, то логическую серию 523 на тиристорах, да с 3-х фазным электропитанием изобретут, то майдан учинят :))
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 23rd, 2015 10:28 pm (UTC)
(Link)
А в чем преимущество для быстродействующих АЦП?
(Reply) (Parent) (Thread)
[User Picture]
From:1500py470
Date:May 23rd, 2015 10:42 pm (UTC)
(Link)
Ключевое с непрецезиоными резисторами. Для традиционой схемы с R/2R нужно добавить больше младших разрядов для компенсации технологических разбросов изготовления -> больше разрядов, больше время на считывание плюс время на обсчёт поправок. А при использовании значений резисторов по ряду фибоначи требуется один раз откалиброваться и записать поправочные коеф. При такой технологии как у нас была в 80е когда военные сидели на заводе в прибалтике и как ОДИН годный скоростной АЦП получался посылали гонца с ним на другой завод в изделее вставить это было спасительным решением. Возможно при развитой технологии это является извращением, но у нас в них толк знали :)) калибровка каждого ацп и прикладывание к нему своего пзу с коэф может изврат, но зато применимый для ритмичного серийного производства
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 23rd, 2015 11:02 pm (UTC)
(Link)
Сильно.
(Reply) (Parent) (Thread)
[User Picture]
From:ramlamyammambam
Date:May 23rd, 2015 10:24 pm (UTC)
(Link)
Это ж можно построить компьютер из белковых молекул, чтобы одни белки по другим ползали.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:May 23rd, 2015 10:29 pm (UTC)
(Link)
Ненадежное это дело.
(Reply) (Parent) (Thread)
[User Picture]
From:ramlamyammambam
Date:May 23rd, 2015 10:37 pm (UTC)
(Link)
Есть мажоритарные схемы, самокорректирующиеся коды и другие хитрости.
(Reply) (Parent) (Thread)
[User Picture]
From:1500py470
Date:May 23rd, 2015 10:44 pm (UTC)
(Link)
Или на муравьях как у Терри Пратчета
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 23rd, 2015 11:03 pm (UTC)
(Link)
Муравьиный феромон годится для "ленивой" стрелки, а с другими будет проблема.
(Reply) (Parent) (Thread)
[User Picture]
From:winpooh
Date:June 15th, 2015 08:38 am (UTC)
(Link)
На муравьях вроде у Хофстадтера в "Goedel, Escher, Bach" было. Только не компьютер, а разумное существо.
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]
From:spamsink
Date:May 26th, 2015 06:43 am (UTC)
(Link)
Неочевидно, как двунаправленность реализовать.
(Reply) (Parent) (Thread)