Тишинуша Гамимеря (spamsink) wrote,
Тишинуша Гамимеря
spamsink

Categories:

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

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


Subscribe

  • Тьюринг был северный осетин

    СЯУ, что имя Alan (тж. Allan, Allen, и пр.) - не просто омоним демонима жителя Северной Осетии-Алании, и даже не просто когнат, а целый дериват.…

  • Фоносемантическая расстыковка

    ...или семантическое насыщение на новый лад. После того, как я несколько раз произнёс про себя "глоссохронология" и "глоттолалия", я на некоторое…

  • Просто так, амбулаторное

    А вы отдавали себе отчёт, что состояние зомби - это, в сущности, состояние амбулаторной смерти?

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 17 comments

  • Тьюринг был северный осетин

    СЯУ, что имя Alan (тж. Allan, Allen, и пр.) - не просто омоним демонима жителя Северной Осетии-Алании, и даже не просто когнат, а целый дериват.…

  • Фоносемантическая расстыковка

    ...или семантическое насыщение на новый лад. После того, как я несколько раз произнёс про себя "глоссохронология" и "глоттолалия", я на некоторое…

  • Просто так, амбулаторное

    А вы отдавали себе отчёт, что состояние зомби - это, в сущности, состояние амбулаторной смерти?