𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On topological dynamics of Turing machines

✍ Scribed by Petr Kůrka

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
874 KB
Volume
174
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We associate to a Turing machine two dynamical systems which we call Turing machine with moving tape (TMT) and Turing machine with moving head (TMH). TMT are equivalent to generalized shifts of and they include two-sided full shifts. TMH are shificommuting maps of two-sided sofic systems. In both classes we characterize systems with the shadowing property, show that a bijective expansive TMT is conjugate to a subshift of finite type and that topological entropy of every TMH is zero. We conjecture that every TMT has a periodic point.

📜 SIMILAR VOLUMES

Simulating Turing machines on Maurer mac
Simulating Turing machines on Maurer machines
✍ J.A. Bergstra; C.A. Middelburg 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 293 KB

In a previous paper, we used Maurer machines to model and analyse micro-architectures. In the current paper, we investigate the connections between Turing machines and Maurer machines with the purpose to gain an insight into computability issues relating to Maurer machines. We introduce ways to simu

On the simulation of quantum turing mach
On the simulation of quantum turing machines
✍ Marco Carpentieri 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 338 KB

In this article we shall review several basic deÿnitions and results regarding quantum computation. In particular, after deÿning Quantum Turing Machines and networks the paper contains an exposition on continued fractions and on errors in quantum networks. The topic of simulation of Quantum Turing M