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?

Improve this question
$\endgroup$
3
  • 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, 2012 at 21:37
  • 3
    $\begingroup$ @AubreydaCunha: make that an answer :). $\endgroup$
    – Joshua Grochow
    Mar 2, 2012 at 21:22
  • $\begingroup$ a related question on another facet (involving also symbolic dynamics) $\endgroup$
    – Nikos M.
    Jun 21, 2014 at 13:53

0

Reset to default

Your Answer

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