A small minimal aperiodic reversible Turing machine
详细信息 查看全文
- 作者：Julien Cassaignea ; julien.cassaigne@univ-mrs.fr" class="auth_mail" title="E-mail the corresponding author ; Nicolas Ollingerb ; 1 ; nicolas.ollinger@univ-orleans.fr" class="auth_mail" title="E-mail the corresponding author ; Rodrigo Torres-Avilé ; sc ; 1 ; 2 ; 3 ; rtorres@ubiobio.cl" class="auth_mail" title="E-mail the corresponding author
- 关键词：Turing machines ; Discrete dynamical systems ; Symbolic dynamics
- 刊名：Journal of Computer and System Sciences
- 出版年：2017
- 出版时间：March 2017
- 年：2017
- 卷：84
- 期：Complete
- 页码：288-301
- 全文大小：402 K
文摘
- class="listitem" id="list_ls0010">
- class="label">•
We present a complete and reversible Turing machine which is aperiodic.
- class="label">•
We prove that its associated dynamical system is time symmetric and minimal.
- class="label">•
The column shift of the presented machine is proved to be substitutive.
- class="label">•
We prove the undecidability of the existence of a periodic orbit in Turing machines.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |