May 23rd, 2015

lenin

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

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

Collapse )