Zigzags in Turing machines

Details Zigzags in Turing machines Zigzags in Turing machines

2010-03-02

arxiv.org/abs/1003.0588v2

Computer Science

Formal Languages and Automata Theory

17p

Scientific paper

We study one-head machines through symbolic and topological dynamics. In particular, a subshift is associated to the subshift, and we are interested in its complexity in terms of realtime recognition. We emphasize the class of one-head machines whose subshift can be recognized by a deterministic pushdown automaton. We prove that this class corresponds to particular restrictions on the head movement, and to equicontinuity in associated dynamical systems.

Affiliated with

Also associated with

No associations

Rating

Zigzags in Turing machines does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Zigzags in Turing machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Zigzags in Turing machines will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-664023