4
$\begingroup$

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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.