<p>On a course, when shift systems were being introduced, the lector said that "if the shift of symbols sequence reminds you Turing machine, then it is a very correct association":</p>

<p>$\sigma(\ldots, x_{-1}, x_0, x_1, \ldots) = (\ldots, x_0, x_1, x_2, \ldots)$</p>

<p>I asked him about concretes but he gave me vague answers that seem to only refer to the general notion of universality that can be proved by reducing a system to Turing machine.</p>

<p>So he did not confirm his suggestion, that shifting sequence of symbols is analogous to moving the tape in Turing machine. But I am confused. Can this be clarified?</p>

CC BY-SA 3.0
2012-02-25T21:37:48.247Z
You may want to take a look at the paper (or maybe just the introduction of) "On Topological Dynamics of Turing Machines" by Kurka.  The introduction is about the connection between the shifts and Turing machines.  He also points out that there is a difference in the dynamics if you think of the head being fixed and the tape moving versus the tape being fixed and the head moving.
Aubrey da Cunha
CC BY-SA 3.0
2012-03-02T21:22:11.763Z
@AubreydaCunha: make that an answer :).
Joshua Grochow
CC BY-SA 3.0
2014-06-21T13:53:09.367Z
a [related question](http://cs.stackexchange.com/q/26049/17369) on another facet (involving also symbolic dynamics)
Nikos M.
<computability><turing-machines><universal-computation>
Are there connections between Turing machines and symbolic dynamic systems?
Mooncer
# Are there connections between Turing machines and symbolic dynamic systems?

(Asked by: username_0 on 2012-02-23)

On a course, when shift systems were being introduced, the lector said that "if the shift of symbols sequence reminds you Turing machine, then it is a very correct association":

$\sigma(\ldots, x\_{-1}, x\_0, x\_1, \ldots) = (\ldots, x\_0, x\_1, x\_2, \ldots)$

I asked him about concretes but he gave me vague answers that seem to only refer to the general notion of universality that can be proved by reducing a system to Turing machine.

So he did not confirm his suggestion, that shifting sequence of symbols is analogous to moving the tape in Turing machine. But I am confused. Can this be clarified?

**Tags:** computability, turing-machines, universal-computation
> **Comments:**
> **username_1**: You may want to take a look at the paper (or maybe just the introduction of) "On Topological Dynamics of Turing Machines" by Kurka.  The introduction is about the connection between the shifts and Turing machines.  He also points out that there is a difference in the dynamics if you think of the head being fixed and the tape moving versus the tape being fixed and the head moving.  
> **username_2**: @AubreydaCunha: make that an answer :).  
> **username_3**: a [related question](http://cs.stackexchange.com/q/26049/17369) on another facet (involving also symbolic dynamics)  

---

## 0 answers

