Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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 Feb 25 '12 at 21:37
@AubreydaCunha: make that an answer :). – Joshua Grochow Mar 2 '12 at 21:22
a related question on another facet (involving also symbolic dynamics) – Nikos M. Jun 21 '14 at 13:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.