Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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|improve this question
3  
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
2  
@AubreydaCunha: make that an answer :). –  Joshua Grochow Mar 2 '12 at 21:22
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.